javabinary-treeheapbinary-heap

Building a binary heap


Im trying trying to build a binary heap by passing it an array of ints. I wanted to know if I should build a class BinaryTree first and then a Heap class in order to implement a binary heap or should I build a single binary heap class? im confused.. thanks!


Solution

  • A binary heap is a special kind of a binary tree. The heap property should be maintained.

    A refresher from Wikipedia: If A is a parent node of B then the key of node A is ordered with respect to the key of node B with the same ordering applying across the heap. Either the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node (this kind of heap is called max heap) or the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node (min heap).

    Depending on your implementation, there will also be some rules about the heap's completeness.

    The binary tree does not necessarily have the Binary Search Tree property.

    So in other words, simply implement the binary heap as a tree with special features as discussed.