Presentation for use with the textbook Algorithm Design and

Applications, by M. T. Goodrich and R. Tamassia, Wiley, 2015

Heaps

xkcd. http://xkcd.com/835/. “Tree.” Used with permission under Creative Commons 2.5 License.
© 2015 Goodrich and Tamassia Heaps 1
 Recall Priority Queue Operations
q  A priority queue stores a q  Additional methods
collection of entries n  min()
q  Each entry is a pair returns, but does not
(key, value) remove, an entry with
smallest key
q  Main methods of the Priority
n  size(), isEmpty()
Queue ADT
q  Applications:
n  insert(k, v)
inserts an entry with key k n  Standby flyers
and value v n  Auctions
n  removeMin() n  Stock market enigines
removes and returns the
entry with smallest key

© 2015 Goodrich and Tamassia Heaps 2

 Recall PQ Sorting
q  We use a priority queue
n  Insert the elements with a series of insert operations
n  Remove the elements in sorted order with a series of removeMin
operations
q  The running time depends on the priority queue implementation:
n  Unsorted sequence gives selection-sort: O(n2) time
n  Sorted sequence gives insertion-sort: O(n2) time
q  Can we do better?

© 2015 Goodrich and Tamassia Heaps 3

 Heaps
q  A heap is a binary tree storing q  The last node of a heap
keys at its nodes and satisfying is the rightmost node of
the following properties: maximum depth
q  Heap-Order: for every internal
node v other than the root,
2
key(v) ≥ key(parent(v))
q  Complete Binary Tree: let h be 5 6
the height of the heap
n  for i = 0, … , h - 1, there are 2i 9 7
nodes of depth i
n  at depth h - 1, the internal nodes
are to the left of the external
nodes last node

© 2015 Goodrich and Tamassia Heaps 4

 Height of a Heap
q  Theorem: A heap storing n keys has height O(log n)
Proof: (we apply the complete binary tree property)
n  Let h be the height of a heap storing n keys
n  Since there are 2i keys at depth i = 0, … , h - 1 and at least one key
at depth h, we have n ≥ 1 + 2 + 4 + … + 2h-1 + 1
n  Thus, n ≥ 2h , i.e., h ≤ log n

depth keys
0 1

1 2
h-1 2h-1

h 1

© 2015 Goodrich and Tamassia Heaps 5

 Heaps and Priority Queues
q  We can use a heap to implement a priority queue
q  We store a (key, element) item at each internal node
q  We keep track of the position of the last node

(2, Sue)

(5, Pat) (6, Mark)

(9, Jeff) (7, Anna)

© 2015 Goodrich and Tamassia Heaps 6

 Array-based Heap Implementation
q  We can represent a heap with n
keys by means of an array of 2
length n
5 6
q  For the node at rank i
n  the left child is at rank 2i
9 7
n  the right child is at rank 2i + 1
q  Links between nodes are not
explicitly stored
q  Operation add corresponds to
inserting at rank n + 1 2 5 6 9 7
q  Operation remove_min 1 2 3 4 5
corresponds to removing at rank n
q  Yields in-place heap-sort

© 2015 Goodrich and Tamassia Heaps 7

 Insertion into a
Heap
q  Method insertItem of the 2
priority queue ADT 5 6
corresponds to the z
9 7
insertion of a key k to
the heap
insertion node
q  The insertion algorithm
consists of three steps 2

n  Find the insertion node z 5 6

(the new last node) z
9 7 1
n  Store k at z
n  Restore the heap-order
property (discussed next)

© 2015 Goodrich and Tamassia Heaps 8

 Upheap
q  After the insertion of a new key k, the heap-order property may be
violated
q  Algorithm upheap restores the heap-order property by swapping k
along an upward path from the insertion node
q  Upheap terminates when the key k reaches the root or a node
whose parent has a key smaller than or equal to k
q  Since a heap has height O(log n), upheap runs in O(log n) time

2 1

5 1 5 2

9 7
z 6 9 7
z 6

© 2015 Goodrich and Tamassia Heaps 9

 Insertion Pseudo-Code
q  Assumes an array-based heap
implementation.

© 2015 Goodrich and Tamassia Heaps 10

 Removal from a Heap
q  Method removeMin of 2
the priority queue ADT
5 6
corresponds to the w
removal of the root key 9 7
from the heap
last node
q  The removal algorithm
consists of three steps 7
n  Replace the root key with
5 6
the key of the last node w w
n  Remove w 9
n  Restore the heap-order
property (discussed next) new last node

© 2015 Goodrich and Tamassia Heaps 11

 Downheap
q  After replacing the root key with the key k of the last node, the
heap-order property may be violated
q  Algorithm downheap restores the heap-order property by
swapping key k along a downward path from the root
q  Upheap terminates when key k reaches a leaf or a node whose
children have keys greater than or equal to k
q  Since a heap has height O(log n), downheap runs in O(log n) time

7 5

5 6 7 6
w w
9 9

© 2015 Goodrich and Tamassia Heaps 12

 RemoveMin Pseudo-code
q  Assumes heap is implemented with an array.

© 2015 Goodrich and Tamassia Heaps 13

 Performance of a Heap
q  A heap has the following performance for the priority queue
operations.

q  The above analysis is based on the following facts:

n  The height of heap T is O(log n), since T is complete.
n  In the worst case, up-heap and down-heap bubbling take time proportional
to the height of T.
n  Finding the insertion position in the execution of insert and updating the
last node position in the execution of removeMin takes constant time.
n  The heap T has n internal nodes, each storing a reference to a key and a
reference to an element.

© 2015 Goodrich and Tamassia Heaps 14

 Heap-Sort
q  Consider a priority q  Using a heap-based
queue with n items priority queue, we can
implemented by means sort a sequence of n
of a heap elements in O(n log n)
time
n  the space used is O(n)
n  methods insert and q  The resulting algorithm is
removeMin take O(log n) called heap-sort
time q  Heap-sort is much faster
n  methods size, isEmpty, than quadratic sorting
and min take time O(1) algorithms, such as
time insertion-sort and
selection-sort

© 2015 Goodrich and Tamassia Heaps 15

 Merging Two Heaps
3 2
q  We are given two two
8 5 4 6
heaps and a key k
q  We create a new heap
with the root node 7
storing k and with the 3 2
two heaps as subtrees 8 5 4 6
q  We perform downheap
to restore the heap-
2
order property
3 4
8 5 7 6

© 2015 Goodrich and Tamassia Heaps 16

 Bottom-up Heap Construction
q  We can construct a heap
storing n given keys in
using a bottom-up
2i -1 2i -1
construction with log n
phases
q  In phase i, pairs of
heaps with 2i -1 keys are
merged into heaps with
2i+1-1 keys
2i+1-1

© 2015 Goodrich and Tamassia Heaps 17

 Example

16 15 4 12 6 7 23 20

25 5 11 27

16 15 4 12 6 7 23 20

© 2015 Goodrich and Tamassia Heaps 18

 Example (contd.)

25 5 11 27

16 15 4 12 6 9 23 20

15 4 6 23

16 25 5 12 11 9 27 20

© 2015 Goodrich and Tamassia Heaps 19

 Example (contd.)
7 8

15 4 6 23

16 25 5 12 11 9 27 20

4 6

15 5 8 23

16 25 7 12 11 9 27 20

© 2015 Goodrich and Tamassia Heaps 20

 Example (end)
10

4 6

15 5 8 23

16 25 7 12 11 9 27 20

5 6

15 7 8 23

16 25 10 12 11 9 27 20

© 2015 Goodrich and Tamassia Heaps 21

 Analysis
q  We visualize the worst-case time of a downheap with a proxy path
that goes first right and then repeatedly goes left until the bottom
of the heap (this path may differ from the actual downheap path)
q  Since each node is traversed by at most two proxy paths, the total
number of nodes of the proxy paths is O(n)
q  Thus, bottom-up heap construction runs in O(n) time
q  Bottom-up heap construction is faster than n successive insertions
and speeds up the first phase of heap-sort, which takes O(n log n)
time in its second phase.

© 2015 Goodrich and Tamassia Heaps 22