length[A]: the size of the array
heap-size[A]: the number of items stored into the array A
Heap is implemented as an array, but its operations can be grasped more easily by looking at the binary tree representation. The mapping between the array representation and binary tree representation is unambiguous. The array representation can be achieved by traversing the binary tree in level order.
Figure 1: Binary tree and array representation for the MaxHeap containing elements (that has the priorities) [16,14,10,8,7,9,3,2,4,1].
Lets consider the i:th node in a Heap that has the value A[i]
||Return the index of the father node|
||Return the index of the left child|
||Return the index of the right child|
Example 1: In Figure 1, node i=3 (
father at index
PARENT(3) = 3/2 = 1 (
A = 16). In addition,
its left and right children are at
LEFT(3) = 2*3 =
RIGHT(3) = 2*3 + 1 = 7 (
A = 9 and
This document was last updated 30.5.2011. Please send your comments to Mikko Laakso, Ari Korhonen, and Ville Karavirta.