PriorityQueue: Tree Implementation

  • Enumerate the structure and order properties of the binary heap.

We are going to explore a tree-based implementation of PriorityQueue. This implementation is called a Binary Heap (or simply a Heap).

A heap has the following properties:

  • Structure (shape) property: heap is a complete binary tree.

The structure property implies the height of the tree is $\Omicron(\lg n)$.1

  • Order (heap) property: the element stored at each node has "better" (i.e. closer to the front) priority than its children.

The order property implies the "best" element is always at the root.

1 We know the height of a perfect binary tree is $\Omicron(\lg n)$. We should prove the complete binary tree also has a logarithmic height. We'll leave that to you to justify this. The proof is not difficult but it is beyond the scope of this course.