CS 124 Section 1
Binary Min/Max Heaps
Yash Nair
February 2021
Yash Nair Section 1 February 2021 1 / 25
Table of Contents
What is a Heap and Why do we Use Them? Heap Basics
Representing a Heap Implementing Heap Operations Problems
Yash Nair Section 1 February 2021 2 / 25
Purpose of Heaps
Data structure to find (and also remove) most extreme (i.e., maximal or minimal) element in a set we can add to quickly
MAX-HEAP finds maximal element, MIN-HEAP finds minimal
We will consider MAX-HEAP, but note that a MIN-HEAP is just a
MAX-HEAP if we multiply the elements by −1
Yash Nair Section 1 February 2021 3 / 25
Using a Sorted Array is Slower than a Heap
Do the following operations using a sorted array: insert 5, insert 3, insert 2, find and remove max, find and remove max, insert 1
Yash Nair Section 1 February 2021 4 / 25
Comparing Operation Times
Data Structure
Add Element
Find Max
Find and Remove Max
Build from Unsorted Array
Sorted Array
O(n)
O (1)
O (1)
O(n log n)
Unsorted Array
O (1)
O(n)
O(n)
O (1)
Binary Heap
O(log n)
O (1)
O(log n)
O(n)
Yash Nair Section 1 February 2021 5 / 25
Heap Operations Overview
PEEK(): what is the largest element in the heap? EXTRACTMAX(): remove the largest element from the heap INSERT(x): insert the element x into the heap
BUILD-HEAP(A): given an unsorted array, A, build a binary heap
Want to be able to do these operations quickly by using a binary tree structure.
Yash Nair Section 1 February 2021 6 / 25
If x is a parent of y in th
e binary tree, then x > y
Representing a Heap
Binary Trees as Arrays Example
ill be used to represent the following max-heap
24, à9, 2, 5à, , à, 5 24
à9
2
5à à 5
l the first element in the heap element 1. Now, given an element i, we can find its l hildren with a little arithmetic:
Yash Nair Section 1 February 2021 7 / 25
ay to represent binary trees more easily is to use an 1-indexed array. For example, the fol w
e
Binary Trees as Arrays
Can order elements of left-aligned binary tree and view them in array
Letting the first element (i.e., root) of tree have index 1, what are the following:
PARENT(i) = LEFT(i) = RIGHT(i) =
Yash Nair Section 1 February 2021 8 / 25
cient way to do this is to use a binary tree to store the list of numbers. This won’t re
y binary tree, but one that satisfies the h
ap property, which is:
If x is a parent of y in the binary tree, then x>y Heap Representation
Representing a Heap
y to represent binary trees more easily is to use an 1-indexed array. For example, the fo
Heap property: if x is a parent of y in the binary tree, then x > y ill be used to represent the following max-heap
A heap is a binary tree that satisfies the heap property
24, à9, 2, 5à, , à, 5 24
à9
2
5à à 5
l the first element in the heap element 1. Now, given an element i, we can find its l
hildren with a little arithmetic:
Yash Nair Section 1 February 2021 9 / 25
al w
e
• Right i = 2i +
Max-Heapify(H , N ) 1.3 Heap operations
Before we look at how peek, insertion and deletion work, let’s first implement some helper functions that will be useful for maintaining the heap structure and building a heap from scratch.
Input: N is node in the left-aligned binary tree H such that the N is 1.3.1 Max-Heapify
the root of a MAX-HEAP, except that N may be smaller than its Max-Heapify(H,N): Given that the children of the node N in the Max-Heap H are each the
children (i.e., but all lower layers satisfy the heap property)
root of a Max-Heap, rearranges the tree rooted at N to be a Max-Heap. We will call this when we break the heap property in order to fix it.
Goal: Rearrange nodes so that tree rooted at N is a MAX-HEAP Max-Heapify(H, N )
Require: N is the root of a Max-Heap except, possibly, at N (i.e., N could be smaller than its children)
1: 2: 3: 4: 5: 6: 7: 8: 9:
l,r Left N ,Right N
if Exists(l)andHl >HN then
largest l
else
largest N
end if
if Exists(r) and H r > H largest then
largest r
end if
if largest 6= N then
10:
11:
12:
13:
Ensure: N is the root of a Max-Heap
Swap(H N , H largest )
Max-Heapify(H, largest) end if
Yash Nair Section 1 February 2021 Description: First, we set larger to be the bigger of N and `, the value of the node N or its left
10 / 25
e 2.
Example
n Max-Heapify with N = on
Run Max-Heapify with N = 1 on the below graph. What is the runtime?
H= à,5,à,3,9,4,,8,6 à
5 à
3 9 4
86
Yash Nair
Section 1
February 2021
11 / 25
u
ote that every level besides the one with N = does satisfy the max-heap property. Tha
Runtime of Max-Heapify
O(log n) comparisons are made O(log n) swaps are made
Total runtime: O(log n).
Yash Nair Section 1 February 2021 12 / 25
•
• Runs in O log n time because node N is moved down at most log n timesà à3à2 Build-Heap
Building a Heap
Build-Heap A : Given an unordered array, makes it into a max heapà à3à2 Build-Heap
Build-Heap A : Given an unordered array, makes it into a max heapà Algorithm 2 Build-Heap A
Require: A is an arrayà Algorithm 2 Build-Heap A
Require: Afoisrania=rraybà length A 2 c down to do
fori=blengthA 2cdowntodo Max-Heapify A,i
Max-Heapify A,i end for end for
Description: Begin at the leaf nodes and call max-heapify so that gradually, the all the elements, Description: Begin at the leaf nodes and call max-heapify so that gradually,
starting at the bottom, will follow the heap propertyà
Idea: Start sftraormtinlgaast tnhoedbeotwtoimth, wcihllilfdollaonwdthweohrekapupropertyà
Exercise 3 à
Run Bui•ldR-uHnEeBxaueiplrdc-oiHsnea:p3onàA = 2, , 4, 3, 6, 5
• Run Build-HeaponA= 2,,4,3,6,5 4
2
2
365
4
• Running time loose upper bound :
Yash Nair Section 1 February 2021 13 / 25
Runtime of Build-Heap
Naive runtime analysis: O(n) calls to Max-Heapify, each takes O(log n) time, so O(n log n)
Tighter analysis:
When we run Max-Heapify from node of height h, runtime is O(h) Build-Heap does this for heights h = 0, . . . , ⌊log n⌋
At most ⌈n/2h+1⌉ nodes at height h (Proof: induction on h. BC:
h = 0; there are at most ⌈n/2⌋ nodes at height 0. IS: remove last layer, then new tree has at most n − ⌈n/2⌋ nodes and height h in original tree is now height h − 1, so, by IH, at most (n − ⌈n/2⌋)/2h ≤ ⌈n/2h+1⌉) Gives runtime bound of
⌊log n⌋
⌈ n ⌉O(h)=Onh
log n 2h+1 2h
h=0 h=0 logn ∞ ∞ h
h 1.5h 3
2h≤ 2h= 4=4,
h=0 h=0 h=0
so runtime is O(n)
Yash Nair Section 1 February 2021 14 / 25
Peek
Q: How to return the maximum element of MAX-HEAP, H, quickly? A: Return H[0] (i.e., the root)! Guaranteed to be maximal by
Build-Heap.
Yash Nair Section 1 February 2021 15 / 25
Solutionà
You would simply return H à because the root of the max heap is guaranteed to be the largest
elementà This runs in O timeà Extract-Max
maintained:
Extract-Max H : Remove the element with the largest value from the heap and Þx everything so that the heap structure is maintainedà
Algorithm 3 *
Extract-Max H
Require: H is a non-empty Max-Heap
max H root
H root H Size H {last element of the heapà} SizeH =
Max-Heapify H,root
return max
Description: Once we remove the max the root , we need to replace it with something thatÕs already in the treeà We choose to take one of the leaves and move it to the root and then max- heapify the heapà
à3à4 Extract-Max
Remove largest element of heap, and ensure that heap structure is
Exercise 5 à
• Run Extract-MaxonH= 6,3,5,2,,4à
24
35
• What is Extract-MaxÕs run time
Yash Nair Section 1 February 2021 16 / 25
5
in H without removing it , how would you do so What is the run time
Runtime of Extract-Max
You would simply return H à because the root of the max heap is guaranteed to be the largest
Solutionà
elementà This runs in O timeà à3à4 Extract-Max
Extract-Max H : Remove the element with the largest value from the heap and Þx everything so that the heap structure is maintainedà
Algorithm 3 *
Extract-Max H
Require: H is a non-empty Max-Heap
max H root
H root H Size H {last element of the heapà} SizeH =
Max-Heapify H,root
return max
Description: Once we remove the max the root , we need to replace it with something thatÕs
already in the treeà We choose to take one of the leaves and move it to the root and then max- Since we only perform one Max-Heapify: O(log n)
heapify the heapà Exercise 5 à
• Run Extract-MaxonH= 6,3,5,2,,4à
Yash Nair Section 1 February 2021 17 / 25
•
the last element It is guarante with children , and then Max-
ed to be a leafà It would be much harder to pluck out Heapify is used to maintain the heap structure:
Insert
4,3,5,2, ! 5,3,4,2,
• O log n because weÕre performing just one max-heapify operationà à3à5 Insert
Insert H,v : Add the value v to the heap Hà
Algorithm 4 Insert H, v
Require: H is a Max-Heap, v is a new valueà
SizeH +=
H Size H v {Set v to be in the next empty slotà}
N Size H {Keep track of the node currently containing và} whileNisnottherootandHParentN
largest l
else
largest N
end if
if Exists(r) and H r > H largest then
largest r
end if
if largest 6= N then
10:
11:
12:
13:
Ensure: N is the root of a Max-Heap
Swap(H N , H largest )
Max-Heapify(H, largest) end if
Yash Nair
Section 1
February 2021
23 / 25
Description: First, we set larger to be the bigger of N and `, the value of the node N or its left
2. Tightness of Runtime Analyses
a.) Show that the O(logn) upper-bound on Max-Heapify’s runtime is tight. In other words, construct an infinite family of arrays, {An}∞n=1, with An a MAX-HEAP except, possibly, at the root (i.e., the root may be smaller than at least one of its children), and length(An) = n for all n, so that the running time, T(n), of Max-Heapify(An,1) is Ω(logn).
b.) Let {An}∞n=1 be any infinite family of arrays with length(An) = n. Prove that the running time, T(n), of Build-Heap(An) is Θ(n).
Yash Nair Section 1 February 2021 24 / 25
3. Sorting with a MAX-HEAP
Consider the following sorting algorithm: run Build-Heap, then repeatedly Extract-Max and append to a sorted list. How efficient is this algorithm? Give a tight bound on the running time.
Yash Nair Section 1 February 2021 25 / 25