Operations on a Heap

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

InsertKey

GetMaxKey

ExtractMaxKey

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.

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 .

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

Below is the runner class:

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  🙂