Heap
Max Heap
Min Heap
Overview
If you've analyzed the visuals of the animation, you may already guess what a Heap is (minx and max). Still, lets summarize it!
A Heap (Binary Heap in particular) is just a type of tree data structure, in particular - a type of a complete binary tree. Heap is either Max Heap or Min Heap (as you already saw in the animation).
In very simple words - Max Heap means that the root node contains the greatest value and each child nodes contains a value that is lesser than its parent.
The opposite is true for Min Heap - the root node is the smallest value, and any child node has a value that is greater than its parent.
This condition for Max and Min heap is called 'Heap property'. And the process of 'converting' a binary tree into a heap by arranging its node to satisfy the heap property is called 'Heapify'.
It's important to note that the nodes in a heap are not sorted. They are considered partially order because we know (in Max heap, for instance) that the 2 children of the root have lower values. But we don't know how each child compares to the other.
Now that we now what a Heap is, we can bravely guess some of its main use cases in computer science - the obvious one is finding a min/max value of a dataset quickly/in constant time. Obvious because we already mentioned that the root node of a heap contains either the lowest or the greatest value. So, for instance, if we want to get the lowest value of a min heap, we directly get the root.
Other use cases are - using heap in priority queues, shortest paths algorithms for graphs, in HeapSort sorting algorithm and others.
In the next section we will take a look at Heap operations.
Code
def max_heapify(arr, n, i):
largest = i
left, right = 2 * i + 1, 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
max_heapify(arr, n, largest)
def min_heapify(arr, n, i):
smallest = i
left, right = 2 * i + 1, 2 * i + 2
if left < n and arr[left] < arr[smallest]:
smallest = left
if right < n and arr[right] < arr[smallest]:
smallest = right
if smallest != i:
arr[i], arr[smallest] = arr[smallest], arr[i]
min_heapify(arr, n, smallest)
def build_max_heap(arr):
n = len(arr)
for i in range(n//2 - 1, -1, -1):
max_heapify(arr, n, i)
def build_min_heap(arr):
n = len(arr)
for i in range(n//2 - 1, -1, -1):
min_heapify(arr, n, i)
data = [50, 40, 20, 30, 15, 8, 7]
# Max Heap
build_max_heap(data.copy())
print("Max Heap:", data)
# Min Heap
build_min_heap(data)
print("Min Heap:", data)
function maxHeapify(arr, n, i) {
let largest = i;
const left = 2 * i + 1;
const right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
maxHeapify(arr, n, largest);
}
}
function minHeapify(arr, n, i) {
let smallest = i;
const left = 2 * i + 1;
const right = 2 * i + 2;
if (left < n && arr[left] < arr[smallest]) smallest = left;
if (right < n && arr[right] < arr[smallest]) smallest = right;
if (smallest !== i) {
[arr[i], arr[smallest]] = [arr[smallest], arr[i]];
minHeapify(arr, n, smallest);
}
}
function buildMaxHeap(arr) {
const n = arr.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) maxHeapify(arr, n, i);
}
function buildMinHeap(arr) {
const n = arr.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) minHeapify(arr, n, i);
}
let data = [50, 40, 20, 30, 15, 8, 7];
// Max Heap
buildMaxHeap(data.slice());
console.log("Max Heap:", data);
// Min Heap
buildMinHeap(data);
console.log("Min Heap:", data);
public class HeapExample {
private static void maxHeapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
maxHeapify(arr, n, largest);
}
}
private static void minHeapify(int[] arr, int n, int i) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] < arr[smallest]) smallest = left;
if (right < n && arr[right] < arr[smallest]) smallest = right;
if (smallest != i) {
int temp = arr[i];
arr[i] = arr[smallest];
arr[smallest] = temp;
minHeapify(arr, n, smallest);
}
}
private static void buildMaxHeap(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) maxHeapify(arr, n, i);
}
private static void buildMinHeap(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) minHeapify(arr, n, i);
}
public static void main(String[] args) {
int[] data = {50, 40, 20, 30, 15, 8, 7};
// Max Heap
buildMaxHeap(data.clone());
System.out.print("Max Heap: ");
for (int value : data) System.out.print(value + " ");
System.out.println();
// Min Heap
buildMinHeap(data);
System.out.print("Min Heap: ");
for (int value : data) System.out.print(value + " ");
System.out.println();
}
}
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Function to convert an array to max heap
void maxHeapify(int arr[], int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
maxHeapify(arr, n, largest);
}
}
// Function to convert an array to min heap
void minHeapify(int arr[], int n, int i) {
int smallest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] < arr[smallest])
smallest = l;
if (r < n && arr[r] < arr[smallest])
smallest = r;
if (smallest != i) {
int temp = arr[i];
arr[i] = arr[smallest];
arr[smallest] = temp;
minHeapify(arr, n, smallest);
}
}
int main() {
int data[] = {50, 40, 20, 30, 15, 8, 7};
int n = sizeof(data) / sizeof(data[0]);
// Convert to Max Heap
for (int i = n / 2 - 1; i >= 0; i--)
maxHeapify(data, n, i);
// Convert to Min Heap
for (int i = n / 2 - 1; i >= 0; i--)
minHeapify(data, n, i);
printf("Max Heap: ");
for (int i = 0; i < n; i++)
printf("%d ", data[i]);
printf("\n");
printf("Min Heap: ");
for (int i = 0; i < n; i++)
printf("%d ", data[i]);
printf("\n");
return 0;
}
function maxHeapify(&$arr, $n, $i) {
$largest = $i;
$left = 2 * $i + 1;
$right = 2 * $i + 2;
if ($left < $n && $arr[$left] > $arr[$largest]) $largest = $left;
if ($right < $n && $arr[$right] > $arr[$largest]) $largest = $right;
if ($largest != $i) {
[$arr[$i], $arr[$largest]] = [$arr[$largest], $arr[$i]];
maxHeapify($arr, $n, $largest);
}
}
function minHeapify(&$arr, $n, $i) {
$smallest = $i;
$left = 2 * $i + 1;
$right = 2 * $i + 2;
if ($left < $n && $arr[$left] < $arr[$smallest]) $smallest = $left;
if ($right < $n && $arr[$right] < $arr[$smallest]) $smallest = $right;
if ($smallest != $i) {
[$arr[$i], $arr[$smallest]] = [$arr[$smallest], $arr[$i]];
minHeapify($arr, $n, $smallest);
}
}
function buildMaxHeap(&$arr) {
$n = count($arr);
for ($i = floor($n / 2) - 1; $i >= 0; $i--) maxHeapify($arr, $n, $i);
}
function buildMinHeap(&$arr) {
$n = count($arr);
for ($i = floor($n / 2) - 1; $i >= 0; $i--) minHeapify($arr, $n, $i);
}
$data = array(50, 40, 20, 30, 15, 8, 7);
// Max Heap
buildMaxHeap($data);
echo "Max Heap: " . implode(" ", $data) . "\n";
// Min Heap
buildMinHeap($data);
echo "Min Heap: " . implode(" ", $data) . "\n";