IT 279: Algorithms and Data Structures, Week 6 Heap

Priority Queues

could be implemented as a list, but that has efficiency issues.

At least one of insertion and deletion will be O(n).

Binary heaps are an alternative that offers better performance

 

Min Binary Heap: Min binary tree + a complete tree(insert from the left child)

percolate up: when inserting a smaller value in a min binary heap

Constant to insert the value at the end.

Must swap with a parent at most height of the tree -1 times.

Height: O(log n) b/c complete tree

 

delete minimum

1. replace the root value with the last value in the heap (reduce the size of the heap)

2. Fix the Heap: Percolate Down (if the smallest child is smaller than the parent, swap)

 

Minimum priority value is in the root:

Constant time to access that node

 

Heap Drawback

Often want to maintain FIFO ordering of items with the same priority

Heaps do not do that

 

heapify(max heap):

1. check the last parent node and compare it with their children

2. swap with the largest child if there is a larger one.

3. check again the children until they don't have any children.

 

Progress Check 14 on Heaps

In Big-Oh terms, what is the maximum height of a complete tree with n nodes?

O(log n)

 

True or false: Heaps are normally implemented in arrays.

True

 

Which of the following is used when inserting into a binary heap?

percolateUp

 

 

Which of the following is used when deleting the minimum value from a minimum binary heap?

percolateDown

 

 

Progress Check 15 on More Heaps

Insertion into a binary heap takes: O(log n)

The buildHeap(or heapify) process uses: percolateDown

What is the runtime of the buildHeap(or heapify) process? O(n)