The Binary Heap - University of Central Florida

The Binary Heap - University of Central Florida

The Binary Heap Binary Heap Looks similar to a binary search tree BUT all the values stored in the subtree rooted at a node are greater than or equal to the value stored at the node. In a min heap that is. We will mainly talk about min heaps, but its the same concept. Binary Heap What are they used for? Priority Queue Performing Heapsort Binary Heap Priority Queue A queue where you always extract the item with the highest priority next. What operations do we need? An efficient deleteMin() and Insert() For our implementation we will achieve O(log n) time for the deleteMin() and Insert() operations. Binary Heap Balanced binary tree Can even store a binary heap in an array instead of an actual binary tree. The children of node i are nodes 2i and 2i+1. Consider: 0 10 20 30 40 50 60 70 80

90 100 110 120 130 1 2 3 4 5 6 7 8 9 10 11 12 13 Draw the tree What node is the parent of node i? Floor(i/2) Binary Tree 0 10

20 30 40 50 60 70 80 90 100 110 120 130 1 2 3 4 5 6 7 8 9 10 11 12

13 10 20 30 40 80 50 90 100 60 110 120 70 130 Heap Operation : Insert Insert into the next open spot in the heap, or the next array location. This will keep the heap balanced. However, in all likelihood this is not where the element belongs Thus we have to do the Percolate Up procedure For example, if you inserted 25 into the next open spot, it would be out of order. Percolate Up If the parent of the new node is greater than the inserted value, swap them. This is a single percolate up step. Continue this process until the inserted nodes parent stores a number lower than it.

Since the height of the tree is O(lg n), this is an O(lg n) operation. What does this remind you of? Insert Consider the tree we had before Insert 65 Where do you insert it? 10 20 30 40 80 50 90 100 60 110 120 70 130 25 Now what? Insert Consider the tree we had before Insert 65 Where do you insert it? 10 20

30 40 80 50 90 100 60 110 120 70 130 25 Insert Consider the tree we had before Insert 65 Where do you insert it? 10 20 30 40 80 50 90 100 25

60 110 120 130 70 Insert Consider the tree we had before Insert 65 Where do you insert it? 10 25 20 40 80 50 90 100 60 110 120 30 130 70 Heap Operation: deleteMin First part is easy Just return the value stored in the root.

Then what do we replace it with? Place the last node in the vacated root. Probably not the correct location. Percolate Down Percolate Down Compare the element to its children. If one of the children is less than the node, swap the lowest. This is a single percolate down step. CONTINUE until this last node has children with larger values than it. Real life example Heap Operation: Heapify Heapify or Bottom-Up Heap Construction How to construct a heap out of unsorted elements. 1) Place all the unsorted elements in a complete binary tree. 2) Going through the nodes in backwards order, and skipping the leaf nodes, run Percolate Down on each of these nodes. Notice that each subtree below any node that has already run Percolate Down is already a heap. So after we run Percolate Down on the root, the whole tree is a heap. Heapify Lets run Heapify on the following elements: 0 80 110 90 30 60

120 40 10 50 100 70 20 130 1 2 3 4 5 6 7 8 9 10 11 12 13 80 110 90

30 10 60 50 Where do we start? 100 120 70 20 40 130 Heapify Lets run Heapify on the following elements: 0 80 110 90 30 60 20 40 10 50 100

70 120 130 1 2 3 4 5 6 7 8 9 10 11 12 13 80 110 90 30 10 60 50

Where do we look next? 100 40 20 70 120 130 Heapify Lets run Heapify on the following elements: 0 80 110 90 30 60 20 40 10 50 100 70 120 130 1

2 3 4 5 6 7 8 9 10 11 12 13 80 110 90 30 10 60 50 Where do we look next? 100 40 20

70 120 130 Heapify Lets run Heapify on the following elements: 0 80 110 90 30 60 20 40 10 50 100 70 120 130 1 2 3 4 5 6

7 8 9 10 11 12 13 80 110 90 10 30 60 50 Where do we look next? 100 40 20 70 120 130 Heapify Lets run Heapify on the following elements: 0

80 110 90 30 60 20 40 10 50 100 70 120 130 1 2 3 4 5 6 7 8 9 10

11 12 13 80 110 20 10 30 60 50 100 90 70 120 40 130 Heapify Lets run Heapify on the following elements: 0 80 110 90 30 60 20

40 10 50 100 70 120 130 1 2 3 4 5 6 7 8 9 10 11 12 13 80 110 20

10 30 60 50 Where do we look next? 100 90 70 120 40 130 Heapify Lets run Heapify on the following elements: 0 80 110 90 30 60 20 40 10 50 100

70 120 130 1 2 3 4 5 6 7 8 9 10 11 12 13 80 10 20 110 10 30 60 50

100 90 70 120 40 130 Heapify Lets run Heapify on the following elements: 0 80 110 90 30 60 20 40 10 50 100 70 120 130 1 2 3

4 5 6 7 8 9 10 11 12 13 80 10 20 30 110 60 50 100 90 70 120 40 130

Heapify Lets run Heapify on the following elements: 0 80 110 90 30 60 20 40 10 50 100 70 120 130 1 2 3 4 5 6 7 8 9

10 11 12 13 80 10 20 30 110 60 50 Where do we look next? 100 90 70 120 40 130 Heapify Lets run Heapify on the following elements: 0 80 110 90

30 60 20 40 10 50 100 70 120 130 1 2 3 4 5 6 7 8 9 10 11 12 13

10 80 20 30 110 60 50 100 90 70 120 40 130 Heapify Lets run Heapify on the following elements: 0 80 110 90 30 60 20 40 10 50

100 70 120 130 1 2 3 4 5 6 7 8 9 10 11 12 13 10 30 20 80 110 60

50 100 90 70 120 40 130 Heapify Lets run Heapify on the following elements: 0 80 110 90 30 60 20 40 10 50 100 70 120 130 1 2

3 4 5 6 7 8 9 10 11 12 13 10 30 20 50 110 60 80 100 90 70 120 40

130 Heapify Why can we NOT go through the nodes in forward order? Whats the running time of the algorithm to create a heap? In a heap with n nodes, we run Percolate Down on n/2 of those nodes. The max number of steps of any Percolate Down is? O(log n) Thus an upper bound for Make-Heap is O(n log n) We can do a more careful analysis for a tighter bound for the running time. Make-Heap Analysis On the board. Heap Sort Now that we know the basic operations to perform on a heap, we can use these to sort values using a heap. Basic Idea: 1) Insert all items into a heap 2) Extract the minimum items n times in a row storing the values sequentially in an array. What is the run time of Heap Sort? Since each insert and extraction takes O(lg n) time. This sort works in O(n lg n) time. Lets do an example.

Recently Viewed Presentations

  • Textbook of Palliative Care Communication

    Textbook of Palliative Care Communication

    Communication about Pain Management at End of Life. ... Help patient explore unknown environment of own death and dying. Understand the patient's psychological challenges (anger, resignation), physical symptoms (pain), and their needs or concerns ... Use metaphors to explain, adjectives...
  • Standards of care for Diabetes Mellitus

    Standards of care for Diabetes Mellitus

    Incident rate ( pre 1000 person year) Age groups (years) Estimation of the Prevalence of glucose intolerance in Iran Urban Rural All 2005 2011 IGT 3.2‡ 0.9 4.1 - - DM 2.6 1.0 3.6 2.0 4.5 IFG - - -...
  • General Machine Guarding #204 Workshop/Lab/Field Activity Hydraulic Molding

    General Machine Guarding #204 Workshop/Lab/Field Activity Hydraulic Molding

    General Machine Guarding #204 Workshop/Lab/Field Activity 2-hand control operation Between cycles, the operator places and removes materials in between two die halves Is there employee exposure to a machine guarding hazard?
  • Last resort gap strategy in processing long-distance ...

    Last resort gap strategy in processing long-distance ...

    An ERP study of Japanese honorification: Are honorific features grammaticalized? Poster Presentation, 18th Annual CUNY Conference on Human Sentence Processing, Tucson, Arizona; Kaan, E. (2002). Investigating the effects of distance and number interference in processing subject-verb dependencies: An ERP study.
  • Staking a claim - WordPress.com

    Staking a claim - WordPress.com

    A claim is: An assertion. A proposition. Something that states the argument's main idea or position. Arguable. Not a statement of fact. Not your topic
  • Guidance Department A-F Pam Otten G-N Danny Straub O-Z Debbie ...

    Guidance Department A-F Pam Otten G-N Danny Straub O-Z Debbie ...

    Scholarships (Merit Based)--Primarily Awarded by Colleges . Part of admissions application. May be special scholarships with a separate application/deadline.
  • Philippians 2:12-18 - Bethel Baptist Youth Group

    Philippians 2:12-18 - Bethel Baptist Youth Group

    Philippians 2:12-18 . 12 Therefore, my beloved, as you have always obeyed, not as in my presence only, but now much more in my absence, work out your own salvation with fear and trembling; 13 for it is God who...
  • Jonathan Ledger Presentation - CollegesWales

    Jonathan Ledger Presentation - CollegesWales

    Jonathan Ledger - Global Skills Ledger_x000d_www.globalskillsledger.co.uk. Presentation title - edit in the Master slide. UK Government wishes to work long term to: Enable . systemic reform . of education systems. Support . economic development, growth and sustainability .