5 Implementation

A binary heap is often implemented by an array (vector). Because all the nodes are serialized, and a heap is always balanced, the array implementation offers simplicity and efficiency over other implementations. The flexible array ADT (see module 0036) or C++ vector (in the STL) are particularly useful, as both data structures maintain the number of items in the array.

However, if a heap is used to perform in-place merge sort, then the data structure should be able to attach its storage to whatever address is provided.

For the ease of computation, the serial number of the root is 1. However, in terms of implementation, this wastes one element in a C array. As a result, for efficiency, it is best to shift the indices of nodes by one. This is necessary to perform in place heap sort in an existing array.

 5.1 Heap ADT
 5.2 Heap sort