Heaps

Heaps are a tree based priority queue.

Heap Property

• Complete Tree

• Heap-Ordering property

Complete Binary Tree

• A binary tree T with height h is complete if the all levels have maximum number of nodes possible.

• So levels i < h - 1 have 2ⁱ nodes.

• We also require that level h-1 is filled from left to right

Illustrate. Filling the tree form left to right:

• Know where to insert entries, insertPosition or last node inserted.

• Heaps are minimum height tree for the number of items stored

• So recursive calls are not deeper then needed

Heap-Order Property

In a heap Tree every node stores a key greater then the key stored at its parents.

• Then the minItem is at the root, easy to get

• Note: Heap is not completely sorted

• Not a memory heap

Implementation

HeapPriorityQueue needs

• ArrayTree, T

• Comparator class, comp

• last node, or insertPosition node of T

Insertion – Bubble Up

We insert into last position, but how can we know it is in the correct position.

1. Inserting  entry (k, e)

   1. expandExternal(insertPos)

2. store entry (k, e) at insertPos

3. Heap bubble-up

• bubble sorts the path from insertion to root

• lg(n) time worst case

Removal – Bubble Down

We can not just remove the root from the tree; what should we do?

Put last entry in the root, but then bubble down.

1. Remove min

   1. return root item

2. duplicate last item into root

3. assign new last node

4. delete old last node

5. Heap bubble-down

• bubble sorts the from root, checking both children for greater than.

• lg(n) time worst case

Cost  

Heap Sort

HeapPriorityQueue performs insertions in O(lg k) where k is the size of the queue.  So sorting by building a HeapPriorityQueue can sort a sequence in O(n lg n) where n < k the size of the sequence.

algorithm HeapSort(Sequence inS, Sequence outS)
// sorts  Sequence inS with heap H
// outputs sorted sequence outS

Make Heap H

while inS is not empty do
    remove element from inS
    insert element into H
    end do

while H is not empty do
    remove minimum element from H
    append element to outS
    end do

The cost is O( n lg n)