Binary heap c implementation

applications of binary heaps in data structures and binary heap priority queue implementation c

Dr.SethPatton,United Kingdom,Teacher

Published Date:22-07-2017

Your Website URL(Optional)

Comment

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 ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 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 7.2.1.1 Example We can find the top object in Q(1) time: 3Binary heaps 9 7.2.1.2 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 7.2.1.2 Pop Using our example, we remove 3:Binary heaps 11 7.2.1.2 Pop We promote 7 (the minimum of 7 and 12) to the root:Binary heaps 12 7.2.1.2 Pop In the left sub-tree, we promote 9:Binary heaps 13 7.2.1.2 Pop Recursively, we promote 19:Binary heaps 14 7.2.1.2 Pop Finally, 55 is a leaf node, so we promote it and delete the leafBinary heaps 15 7.2.1.2 Pop Repeating this operation again, we can remove 7:Binary heaps 16 7.2.1.2 Pop If we remove 9, we must now promote from the right sub-tree:Binary heaps 17 7.2.1.3 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 7.2.1.3 Push Inserting 17 into the last heap – Select an arbitrary node to insert a new leaf node:Binary heaps 19 7.2.1.3 Push The node 17 is less than the node 32, so we swap themBinary heaps 20 7.2.1.3 Push The node 17 is less than the node 31; swap themBinary heaps 21 7.2.1.3 Push The node 17 is less than the node 19; swap them

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.