By Alyce Brady
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).
Submit your completed program through Kit, under Binary Tree.
Have fun! And if you have any questions remember I am available through email, Teams, and my office hours. And don't forget the Collaboration Center, which is a great place to work and ask questions too!