Heaps

A heap is a binary tree that satisfies the following properties:

• Shape property
• Order property

By the shape property, we mean that a heap must be a complete binary tree. A complete binary tree has all its levels filled, except possibly for the last, where the leaves must be located as far to the left as possible.

By the order property, we mean that for every node in the heap, the value stored in that node is greater than or equal to the value in each of its children. A heap that satisfies this property is known as max heap.

Alternatively, every node in the heap can have a value less than or equal to the value in each of its children. In this case, we have a min heap.

Heap Implementation

• A heap is efficiently implemented using a linear array i.e. by sequential representation.
• Since a heap is a complete binary tree, a heap of size n is represented in memory using a linear array of size n.
• A node at index i has its left child at 2i, right child at 2i+1 and parent at index i/2.

Operations on Heaps

• Insertion
• Deletion