DataStructures Series #12 – Heap Datastructure

Note: I used a large part of this article – https://guides.codepath.com/compsci/Heaps#removal

The heap is a special tree-based datastructure and an implementation of the Priority Queue Abstract Data Type.

There are two types of heaps:

  • Max Heap
  • Min Heap

Max Heap

The max heap has the following property: For every node x with a parent node y, the value of y must always be lesser or equal to the value of x.

Min Heap

The min heap has the following property: For every node x with a parent node y, the value of y must always be lower or equal to the value of the value of x.

Heaps | CodePath Android Cliffnotes
Image source: https://guides.codepath.com/

Heap Operations

  • Insert(element)
  • Remove()

Insert – Inserts an element into the tree and readjusts the tree to maintain the heap property.

Remove – Removes the root element and readjusts the tree to maintain the heap property.

Implementation

Insert(data)

When a new element is inserted into a heap, it is added in the next empty spot in the heap, in the right most position in the last level of the heap, in order to maintain the full shape of the heap. However, this new item may violate the other key property of the heap, its ordering.

In a min heap, if the parent of the new element is greater than it, it gets swapped with the parent. This element keeps getting bubbled up in the tree until it either reaches the root of the heap or it has been placed in the right order. The check to ensure that the node is in the proper position is that the parent node is greater than the new node.

The same process applies to max heaps as well

Image source: https://guides.codepath.com/

Remove()

When removing from a heap, the root node is always removed. Then, the last element, the right most node in the last level of the heap, is removed and set as the root. This removal process retains the heap shape, but this new ordering may violate the proper ordering of the heap.

In a min heap, if either one of the new element’s children are less than their parent, the new element is swapped with the smaller of the two children. This element keeps getting bubbled down in the tree until it either reaches the last level of the heap or it has been placed in the right position. The same process applies to max heaps as well, but the ordering is such that the children are both greater than the current node.

Image source: https://guides.codepath.com/

The heap datastructure can also be represented easily with an array and manipulated as follows:

  • Parent: (current index – 1) // 2 (round down)
  • Left child: (current index * 2) + 1
  • Right child: (current index * 2) + 2

This way, new elements are always inserted at the end of the array, then the readjusts itself to maintain the heap property.

Inserting 0 will be:

1 – 3 – 2 – 4 – 6 – 5 – 0

Then readjustments takes place as follows:

  1. Start from the last element
  2. Swap element with parent (currentIndex – 1) if parent is greater than element
  3. Repeat step 2 until it is false

PsuedoCode Implementation:

// zero indexed array
array = [1, 3, 2, 4, 6, 5, 0];

 currElem = 0;
 parentElem = 2;
 currElemIndex = 6;
 parentElemIndex = 2;

 while (parentElem > currElem) {
   tmp = currElem;
   array[currElemIndex] = parentElem;
   array[parentElemIndex] = tmp;
   currElemIndex = parentElemIndex;
   parentElemIndex = round_down((currElemIndex - 1) / 2);
   parentElem =  array[parentElemIndex];
 }

After readjustment, the new array becomes:

0 – 3 – 1 – 2 – 4 – 6 – 5 – 2

REFERENCES