Question? Leave a message!

Binary heap c implementation

applications of binary heaps in data structures and binary heap priority queue implementation c
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
ECE 250 Algorithms and Data Structures Binary heaps Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada © 20143 by Douglas Wilhelm Harder. Some rights reserved.Binary heaps 2 Outline In this topic, we will: – Define a binary min-heap – Look at some examples – Operations on heaps: • Top • Pop • Push – An array representation of heaps – Define a binary max-heap – Using binary heaps as priority queuesBinary heaps 3 7.2 Definition A non-empty binary tree is a min-heap if – The key associated with the root is less than or equal to the keys associated with either of the sub-trees (if any) – Both of the sub-trees (if any) are also binary min-heaps From this definition: – A single node is a min-heap – All keys in either sub-tree are greater than the root keyBinary heaps 4 7.2 Definition Important: THERE IS NO OTHER RELATIONSHIP BETWEEN THE ELEMENTS IN THE TWO SUBTREES Failing to understand this is the greatest mistake a student makesBinary heaps 5 7.2 Example This is a binary min-heap:Binary heaps 6 7.2 Example Adding colour, we observe – The left subtree has the smallest (7) and the largest (89) objects – No relationship between items with similar priorityBinary heaps 8 Example We can find the top object in Q(1) time: 3Binary heaps 9 Pop To remove the minimum object: – Promote the node of the sub-tree which has the least value – Recurs down the sub-tree from which we promoted the least valueBinary heaps 10 Pop Using our example, we remove 3:Binary heaps 11 Pop We promote 7 (the minimum of 7 and 12) to the root:Binary heaps 12 Pop In the left sub-tree, we promote 9:Binary heaps 13 Pop Recursively, we promote 19:Binary heaps 14 Pop Finally, 55 is a leaf node, so we promote it and delete the leafBinary heaps 15 Pop Repeating this operation again, we can remove 7:Binary heaps 16 Pop If we remove 9, we must now promote from the right sub-tree:Binary heaps 17 Push Inserting into a heap may be done either: – At a leaf (move it up if it is smaller than the parent) – At the root (insert the larger object into one of the subtrees) We will use the first approach with binary heaps – Other heaps use the secondBinary heaps 18 Push Inserting 17 into the last heap – Select an arbitrary node to insert a new leaf node:Binary heaps 19 Push The node 17 is less than the node 32, so we swap themBinary heaps 20 Push The node 17 is less than the node 31; swap themBinary heaps 21 Push The node 17 is less than the node 19; swap them