COMP 210: Data Structures

Heaps

Introduction and Definition

A Heap is a binary tree in which the data value at every node in the tree is greater than or equal to all of the data in its child subtrees (if it is a MaxHeap) or is less than or equal to all of the data in its child subtrees (if it is a MinHeap).

A Heap can be implemented as a complete binary tree. The add method first adds new data to the end of the tree in breadth-first order (as any complete binary tree would), but then heapifies the tree, repeatedly percolating the newly added node up the tree whenever the child value is greater than its parent (if a MaxHeap) or less than its parent (if a MinHeap). The remove method finds the item to remove and then shifts the last value in the tree to the location of the removed item. This might break the Heap Invariant, though, so it then heapifies the tree by percolating the moved node down the tree whenever the parent value is less than its child (if a MaxHeap) or less than a child (if a MinHeap).

Starter Code

• K_BinaryTree – a Binary Tree interface
• K_CompleteRecBinTree – a recursive Complete Binary Tree (extends K_AbstRecBinTree)
• K_ALCompleteBinTree – a mostly complete non-recursive Complete Binary Tree built on an ArrayList
• K_MaxHeap – an incomplete Heap class

New versions of what you already coded up: * K_AbstRecBinTree – a Binary Tree interface