Heap Operations
Overview
We already know what Heap, Heap Property and Heapify are, as well as the main purpose of a Heap.
Now - what are the main operations we can do with a Heap?
Obviously - extracting/removing min or max value from a heap is the main one. Considering the easy access we have to max/min values in a heap - another operation is 'peak'. Just seeing which value is highest or lowest without doing anything else with it. As shown in the animation - we can also remove specific elements (not necessarily min/max) and, of course, we can add new elements.
Here's a brief for each of the operations:
Insertion - we create a new element, place it in the last possible position in the heap, then heapify the heap so that the new elements gets to the correct place based on its value
Extraction/removal of min/max root - directly remove the root element, then place the last element of heap in its place to 'fill the void' at the root (since, obviously, any tree needs a root). Then heapify the tree again so that it becomes a heap again and all elements are correctly ordered.
Peaking - it's simple, just access the root of the heap
Removal of element at index - First, we need to check if the element we want to remove is actually present. If it's there, then we assign it a very high value. Then we heapify and the highest value we assigned previously will be the last element so we just remove it. The animation shows it in a slightly different way by directly removing the element but it's important to know that the main goal is to move the desired element to the last position and then remove it.
Code
*These examples are meant to be used with the code examples from the previous section (where we build the heap and its main functionality)
def insert_to_max_heap(arr, value):
arr.append(value)
n = len(arr)
i = n - 1
while i > 0:
parent = (i - 1) // 2
if arr[parent] < arr[i]:
arr[parent], arr[i] = arr[i], arr[parent]
i = parent
else:
break
def insert_to_min_heap(arr, value):
arr.append(value)
n = len(arr)
i = n - 1
while i > 0:
parent = (i - 1) // 2
if arr[parent] > arr[i]:
arr[parent], arr[i] = arr[i], arr[parent]
i = parent
else:
break
def remove_at_index(arr, index):
if index >= len(arr):
raise IndexError("Index not present")
arr[index] = 99999 # We need a high value so that heapify will move/replace the desired element to the last position (as seen in animation)
build_min_heap(arr)
arr.pop()
function insertToMaxHeap(arr, value) {
arr.push(value);
let i = arr.length - 1;
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (arr[parent] < arr[i]) {
[arr[parent], arr[i]] = [arr[i], arr[parent]];
i = parent;
} else {
break;
}
}
}
function insertToMinHeap(arr, value) {
arr.push(value);
let i = arr.length - 1;
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (arr[parent] > arr[i]) {
[arr[parent], arr[i]] = [arr[i], arr[parent]];
i = parent;
} else {
break;
}
}
}
function removeAtIndex(arr, index) {
if (index >= arr.length) {
throw new Error("Index out of range");
}
arr[index] = 99999; // By setting a very high number, we make sure that the element will be the last in the 'min' heap
buildMinHeap(arr);
arr.pop();
}
private static void insertToMaxHeap(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
int n = arr.length;
int i = n - 1;
arr[i] = value;
while (i > 0) {
int parent = (i - 1) / 2;
if (arr[parent] < arr[i]) {
int temp = arr[parent];
arr[parent] = arr[i];
arr[i] = temp;
i = parent;
} else {
break;
}
}
}
private static void insertToMinHeap(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
int n = arr.length;
int i = n - 1;
arr[i] = value;
while (i > 0) {
int parent = (i - 1) / 2;
if (arr[parent] > arr[i]) {
int temp = arr[parent];
arr[parent] = arr[i];
arr[i] = temp;
i = parent;
} else {
break;
}
}
}
private static void removeAtIndex(int[] arr, int index) {
if (index >= arr.length) {
throw new IndexOutOfBoundsException("Index not present");
}
arr[index] = 99999; // By setting a very high number, we make sure that the element we delete will be the last in the 'min' heap we create afterwards.
buildMinHeap(arr);
arr = Arrays.copyOf(arr, arr.length - 1);
}
void insertToMaxHeap(int arr[], int *n, int value) {
arr[*n] = value;
(*n)++;
int i = *n - 1;
while (i > 0) {
int parent = (i - 1) / 2;
if (arr[parent] < arr[i]) {
int temp = arr[parent];
arr[parent] = arr[i];
arr[i] = temp;
i = parent;
} else {
break;
}
}
}
void insertToMinHeap(int arr[], int *n, int value) {
arr[*n] = value;
(*n)++;
int i = *n - 1;
while (i > 0) {
int parent = (i - 1) / 2;
if (arr[parent] > arr[i]) {
int temp = arr[parent];
arr[parent] = arr[i];
arr[i] = temp;
i = parent;
} else {
break;
}
}
}
void removeAtIndex(int arr[], int *n, int index) {
if (index >= *n) {
printf("Index not present\n");
return;
}
arr[index] = 99999; // By setting a very high number, we make sure that the element will be the last in the 'min' heap
(*n)--;
buildMinHeap(arr, *n);
}function insertToMaxHeap(&$arr, $value) {
$arr[] = $value;
$n = count($arr);
$i = $n - 1;
while ($i > 0) {
$parent = floor(($i - 1) / 2);
if ($arr[$parent] < $arr[$i]) {
[$arr[$parent], $arr[$i]] = [$arr[$i], $arr[$parent]];
$i = $parent;
} else {
break;
}
}
}
function insertToMinHeap(&$arr, $value) {
$arr[] = $value;
$n = count($arr);
$i = $n - 1;
while ($i > 0) {
$parent = floor(($i - 1) / 2);
if ($arr[$parent] > $arr[$i]) {
[$arr[$parent], $arr[$i]] = [$arr[$i], $arr[$parent]];
$i = $parent;
} else {
break;
}
}
}
function removeAtIndex(&$arr, $index) {
if ($index >= count($arr)) {
throw new Exception("Index not present");
}
$arr[$index] = 99999; // By setting a very high number, we make sure that the element will be the last in the 'min' heap
buildMinHeap($arr);
array_pop($arr);
}