Priority Queues

Heaps: Chapter 13

Section 13.4 (page 506) Heaps and Section 13.6 Applications (page 528) Heap Sort

Earlier we defined a complete binary tree. A heap is a special form of complete binary tree that is useful in many applications.

Definition: A max (min) tree is a tree in which the key value in each node is no smaller (larger) than the key values in its children (if any).
A max heap is a complete binary tree that is also a max tree. A min heap is a complete binary tree that is also a min tree.

Thus we can see a particular application: heaps are used for priority queues where the operations are

1. insert an item
2. remove an item with the largest key

Max heap

Min heap

Since heaps are complete, they are often represented using an array heap. What does completeness buy us?

Remember:

1. parent(i) is at i/2 (truncated) if i != 1. When i=1, i is the root and has no parent
2. lchild(i) is at 2*i if 2i<n. If 2*i>n, then i has no left child
3. rchild(i) is at 2*i+1 if 2i+1<n. If 2*i+1>n, then i has no right child

Max heap Insertion. insert 5, 21, 1 -- Insertions are easy because of the completeness requirement

O(log n) why?

When an element is deleted from the heap it is taken from the root node (always the largest (smallest)).

We need to maintain heap quality of largest at root and also completeness. This makes it easy!

1. take out root
2. replace with last
3. bubble down (find largest child/switch)

Hardest part seems to make a tree a heap to begin with. That is, the Initialization. Figure 13.5 shows an illustration to heapify an initial binary tree. Note that the variable i points to the first node with children. We would know which this is since it is a binary tree and there are 10 elements so the last elements parent is 10/2 or position 5. Only nodes with chidren will be nodes 5,4,3,2,1. Consider in backwards order (i.e., 5,4,3,2,1).
Complexity is O(n) - book did a lot of work to show this but it seems pretty obvious - doesn't it?

We will use this technique below.

Heap Sort:

Remember sorts?

Algorithm	Worse case	Average case
Bubble sort	n(n-1)/2 = O(n2)	n(n-1)/2 =O(n2)
Quicksort	n(n+3)/2 = O(n2)	1.4n logn = O(n logn)
Mergesort	O(n logn)	O(n logn)
Heapsort	3n logn= O(n logn)	3n logn= O(n logn)

Merge sort is a divide and conquer technique (separate into, sort, merge the two sorted parts). Often done with recursion. Problem, it takes a lot of space.

Because of the structure of heaps, heaps can be sorted in the same memory space that they (the heap) are originally located.

See Program 13.8 (page 528). (with somewhat more of a description below)

The algorithm must always maintain the heap property so the first task is to make the original data a heap.

Technique: rather than build a heap from scratch we go from the bottom up and bubble the largest up. Note that this is not time expensive since we have the properties of complete trees and know who each node's parent is.

Specifically, before we do a heap sort, we need to heapify (as illustrated above).

Ok, suppose we now have a heap. Remember that the last node is n and its parent is n/2.

Very informal psuedo code

take root off and replace with last (maintains complete) compare new root with children bubble bigger child up repeat on down until no children reduce size of array by one and loop

Array	1	2	3	4	5	6	7	8	|	9
Key	r	f	p	d	c	b	k	a		y

r off a in front: who would a's children be? 1 -> 2,3

a (1) compare with f and p : promote p (so a at 3 now)

a (3) compare with 6, 7 (b and k) : promote k

a (7) compare with 14, 15 (too high)

Array	1	2	3	4	5	6	7	|	8	9
Key	p	f	k	d	c	b	a		r	y

p off a in front: who would a's children be? 1 -> 2,3

a (1) compare with f and k : promote k (so a at 3 now)

a (3) compare with 6, 7 (b ) : promote b

a (7) compare with 14, 15 (too high)

Array	1	2	3	4	5	6	|	7	8	9
Key	k	f	b	d	c	a		p	r	y

Next step:

Array	1	2	3	4	5	|	6	7	8	9
Key	f	d	b	a	c		k	p	r	y

Complete illustration at Heap Sort and from text Fig13.9

Priority Queues are important for many applications. Heaps provide an excellent implementation of priority queues.

Heapsort is usually slower than quicksort, but it guarantees that sorting will be completed in O(n log n) comparisons of keys, as quicksort cannot always do.