Heaps

Question 1

What is a ‘Priority Queue’ and what operations does it support?

Answer 1

An abstract data type that is similar to a regular queue, with the difference being that every item has a priority associated with it.

Additional Operations: Insert(x), deleteMin(x)

Question 2

What are the runtimes for Linked lists, Balanced BSTs, and Heaps that implement priority queues?

Answer 2

Linked list
1. Insert(x): Theta(1)
2. deleteMin(): Theta(N)

Balanced BST
1. Insert(x): Theta(lnN)
2. deleteMin(): Theta(lnN)

Heaps
1. Insert(x): Theta(1)
2. deleteMin(): Theta(N)
3. Sorting: nlnN

Question 3

What is a ‘heap’ data structure, and what are its traversal equations?

Answer 3

A heap is essentially a ‘complete’ tree stored in ‘level order’ inside an array.

Traversal Equations:
leftChild(i) = 2i
rightChild(i) = 2i+1
parent(i) = [i/2]

Question 4

What are the two types of heaps.

Answer 4

Min-Heap ( >= x): The values of all the nodes in the subtree rooted in n are >= x.

Max-Heap ( <= x): The values of all the nodes in the subtree rooted in n are < = x.

Question 5

What type of tree is stored in a heap?

Answer 5

A complete tree

Question 6

What order do heaps store trees?

Answer 6

Level-order

Question 7

What are the heap operation runtimes?

Answer 7

height: ln N
insert(x): O(lg N)
deleteMin(): O(lg N)
getMin(): Theta (1)

Question 8

How are heaps built?

Answer 8

From the bottom up.

1. Begin with an unordered array.
2. Make sure that all subtrees in the last two layers are heaps.
3. Move up layer by layer.

percolate Down(i) assumes that both subtrees under i are already heaps?