## Introduction

In this post, we will try to put together all the leanings from the previous posts and define the basic operations on a heap. Also, we will try and derive the running time of each such operation and write code for the same.

Also, we will discuss an interesting problem statement which can be easily solved using the heap property.

## Basic Operations on Heap

The heap can support the following basic operations as any other data structure

**IncreaseKey**– Changes the key value of a given node to a new value. It is assumed that the new value is at least as big as the current value. This makes sure that the key exchanges are required only at the top levels and doesn’t propagate till the leaves. Ideally it takes time proportional to O(logN), which is a less strict upper bound. Here, the N is the number of nodes in the heap.**InsertKey**– Inserts a new key to the heap, the key is ideally inserted as the last element in the heap and then a heapify operation might be required based on its key value. Hence the running time is O(logN) as it can at worse if the inserted key is the largest in the heap, it needs to move the key logN times to reach the root.**GetMaxKey**– Returns the element with the largest key from the heap. Worth noting, the element is not removed from the heap just accessed. As the element is located at the root. The operation would be O(1). Just access the first index of the array.**ExtractMaxKey**– Removes the element with the largest key from the heap. The element is removed from the heap and hence the heap property is disturbed and needs to be restored. This takes a heapify operation post removal. Hence, the running time of removal is O(1) + O(logN) which is O(logN)

## Pseudo Code for the Basic Operations

**IncreaseKey**

1 2 3 4 5 6 7 8 |
IncreaseKey(A, i, k) if k < A[i] raise exception . // the increase key is used to increase the key value, the new key must be bigger than the old one. A[i] <- k // assign key at the ith node while i > 1 AND A[i/2] < A[i] // if the control has not reached the root and i's parent has a smaller key than i. exchange A[i] with A[i/2] // exchange the parent and child. i <- i/2 // move the pointer to parent's index. |

**InsertKey**

1 2 3 4 |
InsertKey(A, k) HeapSize++ //Increase Heap Size by 1 A[HeapSize] = negative infinity; // assign the smallest possible number to the newly inserted element. IncreaseKey(A, HeapSize, k) |

**GetMaxKey**

1 2 |
GetMaxKey return A[1] // the array index starts from 1 |

**ExtractMaxKey**

1 2 3 4 5 6 7 8 |
ExtractMaxKey if HeapSize < 1 raise exception // the heap is empty, cannot extract any element. E <- A[1] // store the root(max key) in a variable A[1] <- A[HeapSize] // take the last key from the heap and put it at the root. This disturbs the heap property HeapSize-- // the heap size will decrease by 1 upon removal Heapify(A, 1) // restore the heap property at the root. return E // return the extracted element. |

## Source Code for Heap

The pseudo code for building a heap is already defined in the previous post. Here we will try and write a concrete code so that it can be used for problem solving related to the heap data structure.

We need a heap class to define the basic structure and then we can derive a MaxHeap or a MinHeap as required.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
abstract class Heap { int A[]; int HeapSize; public Heap(int maxSize) { this.HeapSize = 0; this.A = new int[maxSize + 1]; } public Heap() { } public abstract void heapify(int i); public abstract void insert(int N); public void buildHeapFromArray(int[] Array) { this.HeapSize = Array.length; int k = 1; A = new int[HeapSize + 1]; for (int i : Array) { A[k++] = i; } int i = HeapSize / 2; while (i >= 1) { heapify(i); i--; } } } |

We need an array A to store the nodes of the Heap and a class level field called HeapSize to keep track of the current size. It declares two abstract methods

- heapify
- insert

All these methods have specific logic depending upon the type of Heap (Min or Max). Let us implement the MaxHeap

The buildHeapFromArray method takes an array of random elements and creates a heap out of it. If the instance of the Heap is a MaxHeap, this method will create a MaxHeap and vice versa.

Here is the heapify function for the max heap .

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
@Override public void heapify(int i) { int L = 2 * i; int R = L + 1; int swapIndex = i; if (L < HeapSize && A[L] > A[i]) swapIndex = L; if (R < HeapSize && A[R] > A[swapIndex]) swapIndex = R; if (swapIndex != i) { A[i] = A[i] + A[swapIndex]; A[swapIndex] = A[i] - A[swapIndex]; A[i] = A[i] - A[swapIndex]; heapify(swapIndex); } } |

**How to run the program to create a Max Heap out of an array?**

Below is the runner class:

1 2 3 4 5 6 7 8 |
public class PublicHeapRunner { public static void main(String[] args) { Heap H = new MaxHeap(); H.buildHeapFromArray(new int[] { 6, 2, 7, 14, 10, 12, 9, 4, 8, 3, 5 }); System.out.println(Arrays.toString(H.A)); } } |

For the complete code, please checkout the github repository.

Now that we know how to code for a Heap and most of its functions are available in form of programs. Let us solve an interesting problem in the next post.

In case there was a difficulty understanding any part of the code. Please let me know in comments.

Stay Happy & Stay subscribed 🙂