Heap Algorithms
Introduction
• There are several types of heaps, however, we are going to discuss the
binary heap. A binary heap is a data structure, which looks similar to a
complete binary tree. Heap data structure obeys ordering properties
discussed below. Generally, a Heap is represented by an array. Here, we
are representing a heap by H.
• As the elements of a heap is stored in an array, considering the starting
index as 1, the position of the parent node of ith element can be found
at ⌊ i/2 ⌋ . Left child and right child of ith node is at position 2i and 2i + 1.
• A binary heap can be classified further as either a max-heap or a min-
heap based on the ordering property.
Max-Heap
• In this heap, the key value of a node is greater than or equal to the
key value of the highest child.
Hence, H[Parent(i)] ≥ H[i]
Min-Heap
• In mean-heap, the key value of a node is lesser than or equal to the
key value of the lowest child.
Hence, H[Parent(i)] ≤ H[i]
• In this context, basic operations are shown below with respect to
Max-Heap. Insertion and deletion of elements in and from heaps
need rearrangement of elements. Hence, Heapify function needs to
be called.
Array Representation
• A complete binary tree can be represented by an array, storing its
elements using level order traversal.
• Let us consider a heap (as shown below) which will be represented by
an array H.
• Considering the starting index as 0, using level order traversal, the
elements are being kept in an array as follows.
• In this context, operations on heap are being represented with
respect to Max-Heap.
Operations
• You can do the following operations:
• Find:
• Index of the parent
• Index of the left child
• Index of the right child
Insert Method
Insert Method
• To insert an element in a heap, the new element is initially appended
to the end of the heap as the last element of the array.
• After inserting this element, heap property may be violated, hence
the heap property is repaired by comparing the added element with
its parent and moving the added element up a level, swapping
positions with the parent. This process is called percolation up.
• The comparison is repeated until the parent is larger than or equal to
the percolating element.
Algorithm
Analysis
• Initially, an element is being added at the end of the array.
• If it violates the heap property, the element is exchanged with its
parent.
• The height of the tree is log n.
• Maximum log n number of operations needs to be performed.
• Hence, the complexity of this function is O(log n).
Example
• Let us consider a max-heap, as shown below, where a new element 55
needs to be added.
• Initially, 55 will be added at the end of this array.
Example cont..
• After insertion, it violates the heap property. Hence, the element
needs to swap with its parent. After swap, the heap looks like the
following.
• Again, the element violates the property of heap. Hence, it is
swapped with its parent.
• Now, we have to stop.
Heapify Method
Heapify Method
• Heapify method rearranges the elements of an array where the left
and right sub-tree of ith element obeys the heap property.
Algorithm
• When the provided array does not obey the heap property, Heap is
built based on the following algorithm Build-Max-Heap (numbers[]).
Extract Method
Extract Method
• Extract method is used to extract the root element of a Heap.
Following is the algorithm.
Example
• Let us consider the same example discussed previously. Now we want
to extract an element. This method will return the root element of
the heap.
• After deletion of the root element, the last element will be moved to
the root position.
• Now, Heapify function will be called. After Heapify, the following heap
is generated.
