Data Structures & Algorithms – Heaps (e.g. binary heap, Fibonacci heap)
Heaps are a specific kind of tree-based data structure in which the parent node has a specific relationship with its child nodes, such as the parent node being larger or smaller than its child nodes. There are two main types of heaps: binary heaps and Fibonacci heaps.
A binary heap is a complete binary tree in which every node is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) its children. In a max binary heap, the root node is the largest element in the heap, while in a min binary heap, the root node is the smallest element in the heap.
Here is an example of how to implement a binary heap in Python:
class BinaryHeap:
def __init__(self):
self.heap = []
def insert(self, value):
self.heap.append(value)
self._percolate_up()
def extract_max(self):
if self.heap:
max_val = self.heap[0]
self.heap[0] = self.heap.pop()
self._percolate_down()
return max_val
return None
def _percolate_up(self):
idx = len(self.heap) - 1
while idx > 0:
parent = (idx - 1) // 2
if self.heap[parent] < self.heap[idx]:
self.heap[parent], self.heap[idx] = self.heap[idx], self.heap[parent]
idx = parent
else:
break
def _percolate_down(self):
idx = 0
while idx * 2 + 1 < len(self.heap):
left = idx * 2 + 1
right = idx * 2 + 2
if right < len(self.heap) and self.heap[right] > self.heap[left]:
max_child = right
else:
max_child = left
if self.heap[idx] < self.heap[max_child]:
self.heap[idx], self.heap[max_child] = self.heap[max_child], self.heap[idx]
idx = max_child
else:
break
A Fibonacci heap is a specific type of heap data structure, consisting of a collection of min heaps, with the additional property that it can merge two heaps in constant O(1) time and is able to efficiently extract the minimum element in O(log n) amortized time. Fibonacci heaps are used in graph algorithms such as Dijkstra’s shortest path and Prim’s minimum spanning tree.
Here is an example of how to implement a Fibonacci heap in Javascript:
class FibonacciHeap {
constructor() {
this.min = null;
this.size = 0;
}
insert(value) {
let node = {
value,
degree: 0,
parent: null,
child: null,
left: null,
right: null,
mark: false
};
if (this.min) {
node.left = this.min;
node.right = this.min.right;
this.min.right = node;
node.right.left = node;
if (node.value < this.min.value) {
this.min = node;
}
} else {
this.min = node;
}
this.size++;
}
extractMin() {
let min = this.min;
if (min) {
if (min.child) {
let child = min.child;
do {
child.parent = null;
child = child.right;
} while (child !== min.child);
min.left.right = min.child;
min.child.left.right = min.right;
min.right.left = min.child.left;
}
min.left.right = min.right;
min.right.left = min.left;
if (min === min.right) {
this.min = null;
} else {
this.min = min.right;
this._consolidate();
}
this.size--;
}
return min ? min.value : null;
}
_consolidate() {
let array = [];
let start = this.min;
let current = start;
do {
array[current.degree] = current;
current = current.right;
} while (current !== start);
for (let i = 0; i < array.length; i++) {
let x = array[i];
while (array[i]) {
let y = array[i];
if (x.value > y.value) {
let temp = x;
x = y;
y = temp;
}
this._link(y, x);
array[i] = null;
i++;
}
}
}
_link(y, x) {
y.left.right = y.right;
y.right.left = y.left;
y.parent = x;
if (!x.child) {
x.child = y;
y.right = y;
y.left = y;
} else {
y.left = x.child;
y.right = x.child.right;
x.child.right = y;
y.right.left = y;
}
x.degree++;
y.mark = false;
}
}
It’s a bit more difficult to implement Fibonacci heap using only primitives like in the previous examples because Fibonacci heap is a more complex data structure that relies on the properties of the Fibonacci numbers and the specific relationship between parent and child nodes.
In python, for example, the Fibonacci heap can be implemented by creating a class for the heap, another class for the nodes, and then linking the nodes together using properties such as “next” and “prev” to link siblings, and “child” and “parent” to link children and parents.
It’s worth noting that Fibonacci Heaps are not commonly used in practice due to its relatively high constant factors compared to other more efficient data structures like binary heap, which achieves the same time complexity with lower constant factors.
It’s also worth noting that Fibonacci heap is not supported by standard libraries of most programming languages, and it’s not recommended to implement it from scratch if it’s not the main focus of your project.
In Java, a binary heap can be implemented using an array or an ArrayList to store the elements, and using a series of helper methods to maintain the heap property. Here is an example of how to implement a binary heap in Java:
import java.util.ArrayList;
public class BinaryHeap {
ArrayList<Integer> heap;
public BinaryHeap() {
heap = new ArrayList<>();
}
public void insert(int value) {
heap.add(value);
int current = heap.size() - 1;
int parent = (current - 1) / 2;
while (current > 0 && heap.get(current) > heap.get(parent)) {
int temp = heap.get(current);
heap.set(current, heap.get(parent));
heap.set(parent, temp);
current = parent;
parent = (current - 1) / 2;
}
}
public int extractMax() {
if (heap.size() == 0) {
return Integer.MIN_VALUE;
}
int max = heap.get(0);
heap.set(0, heap.get(heap.size() - 1));
heap.remove(heap.size() - 1);
int current = 0;
while (current < heap.size()) {
int left = 2 * current + 1;
int right = 2 * current + 2;
int largest = current;
if (left < heap.size() && heap.get(left) > heap.get(largest)) {
largest = left;
}
if (right < heap.size() && heap.get(right) > heap.get(largest)) {
largest = right;
}
if (largest == current) {
break;
}
int temp = heap.get(current);
heap.set(current, heap.get(largest));
heap.set(largest, temp);
current = largest;
}
return max;
}
}
In Rust, a binary heap can be implemented using a vector and a series of helper methods to maintain the heap property. Here is an example of how to implement a binary heap in Rust:
struct BinaryHeap {
heap: Vec<i32>,
}
impl BinaryHeap {
fn new() -> Self {
Self { heap: Vec::new() }
}
fn insert(&mut self, value: i32) {
self.heap.push(value);
let mut current = self.heap.len() - 1;
let mut parent = (current - 1) / 2;
while current > 0 && self
heap[current] > heap[parent] {
self.heap.swap(current, parent);
current = parent;
parent = (current - 1) / 2;
}
}
fn extract_max(&mut self) -> i32 {
if self.heap.is_empty() {
return i32::min_value();
}
let max = self.heap[0];
self.heap[0] = self.heap.pop().unwrap();
let mut current = 0;
while current < self.heap.len() {
let left = 2 * current + 1;
let right = 2 * current + 2;
let mut largest = current;
if left < self.heap.len() && self.heap[left] > self.heap[largest] {
largest = left;
}
if right < self.heap.len() && self.heap[right] > self.heap[largest] {
largest = right;
}
if largest == current {
break;
}
self.heap.swap(current, largest);
current = largest;
}
max
}
}
It’s worth noting that in Rust, the standard library has a BinaryHeap<T> type in the std::collections::binary_heap module which provides a much more efficient and robust implementation of the binary heap data structure, with many additional features.
I hope this information was helpful in understanding how to implement these data structures from scratch using primitives in Python, Javascript, Java and Rust. As always, it’s important to consider the use case and the context of the project when choosing the appropriate data structure and algorithm.