Min heap
Category: Data Structures
Discover the essentials of Min Heap data structures. Explore how Min Heaps work, their key properties, and learn how to perform operations like insertion, deletion, and heapify with step-by-step examples.
Table of contents
- Insertion in min-heap
- Remove element from the min-heap
- Min heap implementation - Recursive
- Min heap implementation - Iterative
A Min-heap is a data structure in which each node is smaller or equal to its children. It is a tree-based data structure but implemented as an array.
Min-heaps are commonly used to implement priority queues.
Heap always maintains the heap property. For min-heap heap property will be -
Maintaining heap property (for min-heap) means comparing the left child and right child with the root and among all three, the minimum will become the root.
To understand about heap please refer to this article -
Insertion in min-heap
While insertion we have to maintain the heap properties -
- Complete binary tree
- Min heap order
Insertion
Take the example of this heap and try to insert a new node -
Its representation in the form of an array will be like this -
Let's insert 15 into this heap
For insertion, add the new element at the end of the array i.e., insert the new element as a leaf node then move the element to its correct position. Correct position is actually where this node will be lesser than its children and higher than its parent.
We will do this by comparing this new element to its parent at each step and moving this new upwards until it is less than its parent.
Do the same steps again. Compare 15 to its new parent and move this to its correct position.
Now 15 is inserted at its correct position.
The time complexity to insert a new element in a heap will be O(h) where h is the height of the tree. The height of a balanced binary tree is log n so the insertion of a new element will take O(log n) time which is better than what we were getting in the case of the Binary tree implementation of heap. That’s why it's better to store data in the form of an array for a heap.
The process of moving data up is called percolate up or bubble up or heapify up or sift up.
Remove element from the min-heap
This is the main operation of the heap. All the elements will be removed from the 0th index always because the minimum element will always be at index 0. Since we are storing data in such a way.
This is the main purpose of a min heap i.e., whatever data we are storing in the heap we are always sure that while removing the data we will be getting is minimum among all the data stored.
We can say that the minimum element has the highest priority and it will picked up at a given time.
Deletion
Let's try to remove an element from the heap that we created earlier. So, 10 will be removed from the heap. Since this is the root of min-heap.
But if we will remove the root element then the heap will be disturbed and we will have to do some extra operations. So rather than removing the element directly from the root, replace it with the last element from heap and the replace the last element.
Now the root element is removed from the heap but the heap property is disturbed i.e., not all the root elements are lesser than their children.
But that's not a big deal we already know we can do that by just iterating over all the elements comparing the root elements with children and moving the lower element upwards as a root. But this time start with the root element because we know this element is the reason for the disturbance of heap property.
Again let's see if 60 is still greater than its children then move this downwards.
This is the final heap after removing an element. Time complexity will be O(log n) for removing an element.
The process of moving data down is called percolate down or **bubble down or heapify down or sift down.
Min heap implementation - Recursive
Here, we will implement percolate functionality in recursive way.
Python
class MinHeap:
def __init__(self):
# Initialize an empty list to store the heap elements
self.heap = []
def is_empty(self):
# Check if the heap is empty
return len(self.heap) == 0
def get_min(self):
# Return the minimum element without removing it
if self.is_empty():
return None
return self.heap[0]
def get_size(self):
# Return the size of the heap
return len(self.heap)
def insert(self, value):
# Insert the value into the heap
self.heap.append(value)
self._percolate_up(len(self.heap) - 1)
def _percolate_up(self, index):
# Base case: if index is 0, there's no parent to compare with
if index == 0:
return
parent_index = (index - 1) // 2
# If the current element is smaller than its parent, swap and recurse
if self.heap[index] < self.heap[parent_index]:
self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
# Recursively call _percolate_up with the parent index
self._percolate_up(parent_index)
def remove(self):
# Remove and return the minimum element from the heap (root of the heap)
if self.is_empty():
return None
if len(self.heap) == 1:
return self.heap.pop()
root = self.heap[0]
# Move the last element to the root and percolate down
self.heap[0] = self.heap.pop()
self._percolate_down(0)
return root
def _percolate_down(self, index):
# Move the element at the given index down the heap to maintain the heap property
size = len(self.heap)
smallest = index
left = 2 * index + 1
right = 2 * index + 2
# Check if the left child exists and is smaller than the current element
if left < size and self.heap[left] < self.heap[smallest]:
smallest = left
# Check if the right child exists and is smaller than the current smallest
if right < size and self.heap[right] < self.heap[smallest]:
smallest = right
# If the smallest element is not the current element, swap and continue percolating down
if smallest != index:
self.heap[index], self.heap[smallest] = (
self.heap[smallest],
self.heap[index],
)
self._percolate_down(smallest)
min_heap = MinHeap()
min_heap.insert(10)
min_heap.insert(4)
min_heap.insert(9)
min_heap.insert(2)
min_heap.insert(7)
print("Min element peek:", min_heap.get_min())
print("Min element:", min_heap.remove())
print("Min element:", min_heap.remove())
min_heap.insert(5)
print("Min element:", min_heap.remove())
JavaScript
class MinHeap {
constructor() {
// Initialize an empty array to store the heap elements
this.heap = [];
}
isEmpty() {
// Check if the heap is empty
return this.heap.length === 0;
}
getMin() {
// Return the minimum element without removing it
if (this.isEmpty()) {
return null;
}
return this.heap[0];
}
getSize() {
// Return the size of the heap
return this.heap.length;
}
insert(value) {
// Insert the value into the heap
this.heap.push(value);
this.percolateUp(this.heap.length - 1);
}
percolateUp(index) {
// Base case: if index is 0, there's no parent to compare with
if (index === 0) return;
let parentIndex = Math.floor((index - 1) / 2);
// If the current element is smaller than its parent, swap and recurse
if (this.heap[index] < this.heap[parentIndex]) {
[this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
// Recursively call percolateUp with the parent index
this.percolateUp(parentIndex);
}
}
remove() {
// Remove and return the minimum element from the heap (root of the heap)
if (this.isEmpty()) {
return null;
}
if (this.heap.length === 1) {
return this.heap.pop();
}
const root = this.heap[0];
// Move the last element to the root and percolate down
this.heap[0] = this.heap.pop();
this.percolateDown(0);
return root;
}
percolateDown(index) {
// Move the element at the given index down the heap to maintain the heap property
const size = this.heap.length;
let smallest = index;
const left = 2 * index + 1;
const right = 2 * index + 2;
// Check if the left child exists and is smaller than the current element
if (left < size && this.heap[left] < this.heap[smallest]) {
smallest = left;
}
// Check if the right child exists and is smaller than the current smallest
if (right < size && this.heap[right] < this.heap[smallest]) {
smallest = right;
}
// If the smallest element is not the current element, swap and continue percolating down
if (smallest !== index) {
[this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
this.percolateDown(smallest);
}
}
}
const minHeap = new MinHeap();
minHeap.insert(10);
minHeap.insert(4);
minHeap.insert(9);
minHeap.insert(2);
minHeap.insert(7);
console.log("Min element peek:", minHeap.getMin());
console.log("Min element:", minHeap.remove());
console.log("Min element:", minHeap.remove());
minHeap.insert(5);
console.log("Min element:", minHeap.remove());
Java
import java.util.ArrayList;
class MinHeap {
private ArrayList<Integer> heap;
public MinHeap() {
// Initialize an empty list to store the heap elements
heap = new ArrayList<>();
}
public boolean isEmpty() {
// Check if the heap is empty
return heap.size() == 0;
}
public int getMin() {
// Return the minimum element without removing it
if (isEmpty()) {
throw new IllegalStateException("Heap is empty");
}
return heap.get(0);
}
public int getSize() {
// Return the size of the heap
return heap.size();
}
public void insert(int value) {
// Insert the value into the heap
heap.add(value);
percolateUp(heap.size() - 1);
}
private void percolateUp(int index) {
// Base case: if index is 0, there's no parent to compare with
if (index == 0) return;
int parentIndex = (index - 1) / 2;
// If the current element is smaller than its parent, swap and recurse
if (heap.get(index) < heap.get(parentIndex)) {
swap(index, parentIndex);
// Recursively call percolateUp with the parent index
percolateUp(parentIndex);
}
}
public int remove() {
// Remove and return the minimum element from the heap (root of the heap)
if (isEmpty()) {
throw new IllegalStateException("Heap is empty");
}
if (heap.size() == 1) {
return heap.remove(0);
}
int root = heap.get(0);
// Move the last element to the root and percolate down
heap.set(0, heap.remove(heap.size() - 1));
percolateDown(0);
return root;
}
private void percolateDown(int index) {
// Move the element at the given index down the heap to maintain the heap property
int size = heap.size();
int smallest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
// Check if the left child exists and is smaller than the current element
if (left < size && heap.get(left) < heap.get(smallest)) {
smallest = left;
}
// Check if the right child exists and is smaller than the current smallest
if (right < size && heap.get(right) < heap.get(smallest)) {
smallest = right;
}
// If the smallest element is not the current element, swap and continue percolating down
if (smallest != index) {
swap(index, smallest);
percolateDown(smallest);
}
}
private void swap(int i, int j) {
int temp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, temp);
}
public static void main(String[] args) {
MinHeap minHeap = new MinHeap();
minHeap.insert(10);
minHeap.insert(4);
minHeap.insert(9);
minHeap.insert(2);
minHeap.insert(7);
System.out.println("Min element peek: " + minHeap.getMin());
System.out.println("Min element: " + minHeap.remove());
System.out.println("Min element: " + minHeap.remove());
minHeap.insert(5);
System.out.println("Min element: " + minHeap.remove());
}
}
Go
package main
import (
"errors"
"fmt"
)
type MinHeap struct {
heap []int
}
// Initialize a new MinHeap
func NewMinHeap() *MinHeap {
return &MinHeap{
heap: []int{},
}
}
// Check if the heap is empty
func (h *MinHeap) IsEmpty() bool {
return len(h.heap) == 0
}
// Get the minimum element without removing it
func (h *MinHeap) GetMin() (int, error) {
if h.IsEmpty() {
return 0, errors.New("heap is empty")
}
return h.heap[0], nil
}
// Get the size of the heap
func (h *MinHeap) GetSize() int {
return len(h.heap)
}
// Insert a value into the heap
func (h *MinHeap) Insert(value int) {
h.heap = append(h.heap, value)
h.percolateUp(len(h.heap) - 1)
}
// Percolate the element at the given index up to maintain the heap property
func (h *MinHeap) percolateUp(index int) {
// Base case: if index is 0, there's no parent to compare with
if index == 0 {
return
}
parentIndex := (index - 1) / 2
// If the current element is smaller than its parent, swap and recurse
if h.heap[index] < h.heap[parentIndex] {
h.heap[index], h.heap[parentIndex] = h.heap[parentIndex], h.heap[index]
// Recursively call percolateUp with the parent index
h.percolateUp(parentIndex)
}
}
// Remove and return the minimum element from the heap
func (h *MinHeap) Remove() (int, error) {
if h.IsEmpty() {
return 0, errors.New("heap is empty")
}
if len(h.heap) == 1 {
root := h.heap[0]
h.heap = []int{}
return root, nil
}
root := h.heap[0]
// Move the last element to the root and percolate down
h.heap[0] = h.heap[len(h.heap)-1]
h.heap = h.heap[:len(h.heap)-1]
h.percolateDown(0)
return root, nil
}
// Percolate the element at the given index down to maintain the heap property
func (h *MinHeap) percolateDown(index int) {
size := len(h.heap)
smallest := index
left := 2*index + 1
right := 2*index + 2
if left < size && h.heap[left] < h.heap[smallest] {
smallest = left
}
if right < size && h.heap[right] < h.heap[smallest] {
smallest = right
}
if smallest != index {
h.heap[index], h.heap[smallest] = h.heap[smallest], h.heap[index]
h.percolateDown(smallest)
}
}
func main() {
minHeap := NewMinHeap()
minHeap.Insert(10)
minHeap.Insert(4)
minHeap.Insert(9)
minHeap.Insert(2)
minHeap.Insert(7)
minElement, _ := minHeap.GetMin()
fmt.Println("Min element peek:", minElement)
minElement, _ = minHeap.Remove()
fmt.Println("Min element:", minElement)
minElement, _ = minHeap.Remove()
fmt.Println("Min element:", minElement)
minHeap.Insert(5)
minElement, _ = minHeap.Remove()
fmt.Println("Min element:", minElement)
}
C++
#include <iostream>
#include <vector>
#include <stdexcept>
class MinHeap {
private:
std::vector<int> heap;
void percolateUp(int index) {
if (index <= 0) return; // Base case: root of the heap
int parentIndex = (index - 1) / 2;
if (heap[index] < heap[parentIndex]) {
std::swap(heap[index], heap[parentIndex]);
percolateUp(parentIndex); // Recur with the parent index
}
}
void percolateDown(int index) {
int size = heap.size();
int smallest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < size && heap[left] < heap[smallest]) {
smallest = left;
}
if (right < size && heap[right] < heap[smallest]) {
smallest = right;
}
if (smallest != index) {
std::swap(heap[index], heap[smallest]);
percolateDown(smallest);
}
}
public:
MinHeap() {}
bool isEmpty() const {
return heap.empty();
}
int getMin() const {
if (isEmpty()) {
throw std::runtime_error("Heap is empty");
}
return heap[0];
}
int getSize() const {
return heap.size();
}
void insert(int value) {
heap.push_back(value);
percolateUp(heap.size() - 1);
}
int remove() {
if (isEmpty()) {
throw std::runtime_error("Heap is empty");
}
if (heap.size() == 1) {
int root = heap.back();
heap.pop_back();
return root;
}
int root = heap[0];
heap[0] = heap.back();
heap.pop_back();
percolateDown(0);
return root;
}
};
int main() {
MinHeap minHeap;
minHeap.insert(10);
minHeap.insert(4);
minHeap.insert(9);
minHeap.insert(2);
minHeap.insert(7);
std::cout << "Min element peek: " << minHeap.getMin() << std::endl;
std::cout << "Min element: " << minHeap.remove() << std::endl;
std::cout << "Min element: " << minHeap.remove() << std::endl;
minHeap.insert(5);
std::cout << "Min element: " << minHeap.remove() << std::endl;
return 0;
}
Rust
struct MinHeap {
heap: Vec<i32>,
}
impl MinHeap {
fn new() -> Self {
MinHeap { heap: Vec::new() }
}
fn is_empty(&self) -> bool {
self.heap.is_empty()
}
fn get_min(&self) -> Option<i32> {
if self.is_empty() {
None
} else {
Some(self.heap[0])
}
}
fn get_size(&self) -> usize {
self.heap.len()
}
fn insert(&mut self, value: i32) {
self.heap.push(value);
self.percolate_up(self.heap.len() - 1);
}
fn percolate_up(&mut self, index: usize) {
if index == 0 {
return; // Base case: if at the root
}
let parent_index = (index - 1) / 2;
if self.heap[index] < self.heap[parent_index] {
self.heap.swap(index, parent_index);
self.percolate_up(parent_index); // Recursive call
}
}
fn remove(&mut self) -> Option<i32> {
if self.is_empty() {
return None;
}
if self.heap.len() == 1 {
return self.heap.pop();
}
let root = self.heap[0];
self.heap[0] = self.heap.pop().unwrap();
self.percolate_down(0);
Some(root)
}
fn percolate_down(&mut self, index: usize) {
let left = 2 * index + 1;
let right = 2 * index + 2;
let size = self.heap.len();
let mut smallest = index;
if left < size && self.heap[left] < self.heap[smallest] {
smallest = left;
}
if right < size && self.heap[right] < self.heap[smallest] {
smallest = right;
}
if smallest != index {
self.heap.swap(index, smallest);
// Recursive call to continue percolating down
self.percolate_down(smallest);
}
}
}
fn main() {
let mut min_heap = MinHeap::new();
min_heap.insert(10);
min_heap.insert(4);
min_heap.insert(9);
min_heap.insert(2);
min_heap.insert(7);
println!("Min element peek: {:?}", min_heap.get_min());
println!("Min element: {:?}", min_heap.remove());
println!("Min element: {:?}", min_heap.remove());
min_heap.insert(5);
println!("Min element: {:?}", min_heap.remove());
}
Min heap implementation - Iterative
Here, we will implement percolate functionality in iterative way.
Python
class MinHeap:
def __init__(self):
# Initialize an empty list to store the heap elements
self.heap = []
def is_empty(self):
# Check if the heap is empty
return len(self.heap) == 0
def get_min(self):
# Return the minimum element without removing it
if self.is_empty():
return None
return self.heap[0]
def get_size(self):
# Return the size of the heap
return len(self.heap)
def insert(self, value):
# Insert the value into the heap
self.heap.append(value)
self._percolate_up(len(self.heap) - 1)
def _percolate_up(self, index):
# Move the element at the given index up the heap to maintain the heap property
parent_index = (index - 1) // 2
while index > 0 and self.heap[index] < self.heap[parent_index]:
# Swap the current element with its parent if it's smaller
self.heap[index], self.heap[parent_index] = (
self.heap[parent_index],
self.heap[index],
)
index = parent_index
parent_index = (index - 1) // 2
def remove(self):
# Remove and return the minimum element from the heap (root of the heap)
if self.is_empty():
return None
if len(self.heap) == 1:
return self.heap.pop()
root = self.heap[0]
# Move the last element to the root and percolate down
self.heap[0] = self.heap.pop()
self._percolate_down(0)
return root
def _percolate_down(self, index):
# Iteratively move the element at the given index down the heap to maintain the heap property
size = len(self.heap)
while index < size:
smallest = index
left = 2 * index + 1
right = 2 * index + 2
# Check if the left child exists and is smaller than the current element
if left < size and self.heap[left] < self.heap[smallest]:
smallest = left
# Check if the right child exists and is smaller than the current smallest
if right < size and self.heap[right] < self.heap[smallest]:
smallest = right
# If the smallest element is not the current element, swap and continue percolating down
if smallest != index:
self.heap[index], self.heap[smallest] = (
self.heap[smallest],
self.heap[index],
)
index = smallest
else:
break
# Example usage:
min_heap = MinHeap()
min_heap.insert(10)
min_heap.insert(4)
min_heap.insert(9)
min_heap.insert(2)
min_heap.insert(7)
print("Min element peek:", min_heap.get_min()) # Output: 2
print("Min element:", min_heap.remove()) # Output: 2
print("Min element:", min_heap.remove()) # Output: 4
min_heap.insert(5)
print("Min element:", min_heap.remove()) # Output: 5
JavaScript
class MinHeap {
constructor() {
this.heap = [];
}
isEmpty() {
return this.heap.length === 0;
}
getMin() {
return this.isEmpty() ? null : this.heap[0];
}
getSize() {
return this.heap.length;
}
insert(value) {
this.heap.push(value);
this.percolateUp(this.heap.length - 1);
}
percolateUp(index) {
let parentIndex = Math.floor((index - 1) / 2);
while (index > 0 && this.heap[index] < this.heap[parentIndex]) {
[this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
index = parentIndex;
parentIndex = Math.floor((index - 1) / 2);
}
}
remove() {
if (this.isEmpty()) {
return null;
}
if (this.heap.length === 1) {
return this.heap.pop();
}
const root = this.heap[0];
this.heap[0] = this.heap.pop();
this.percolateDown(0);
return root;
}
percolateDown(index) {
const size = this.heap.length;
while (index < size) {
let smallest = index;
const left = 2 * index + 1;
const right = 2 * index + 2;
if (left < size && this.heap[left] < this.heap[smallest]) {
smallest = left;
}
if (right < size && this.heap[right] < this.heap[smallest]) {
smallest = right;
}
if (smallest !== index) {
[this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
index = smallest;
} else {
break;
}
}
}
}
// Example usage:
const minHeap = new MinHeap();
minHeap.insert(10);
minHeap.insert(4);
minHeap.insert(9);
minHeap.insert(2);
minHeap.insert(7);
console.log("Min element peek:", minHeap.getMin()); // Output: 2
console.log("Min element:", minHeap.remove()); // Output: 2
console.log("Min element:", minHeap.remove()); // Output: 4
minHeap.insert(5);
console.log("Min element:", minHeap.remove()); // Output: 5
Java
import java.util.ArrayList;
class MinHeap {
private ArrayList<Integer> heap;
public MinHeap() {
heap = new ArrayList<>();
}
public boolean isEmpty() {
return heap.isEmpty();
}
public Integer getMin() {
return isEmpty() ? null : heap.get(0);
}
public int getSize() {
return heap.size();
}
public void insert(int value) {
heap.add(value);
percolateUp(heap.size() - 1);
}
private void percolateUp(int index) {
int parentIndex = (index - 1) / 2;
while (index > 0 && heap.get(index) < heap.get(parentIndex)) {
swap(index, parentIndex);
index = parentIndex;
parentIndex = (index - 1) / 2;
}
}
public Integer remove() {
if (isEmpty()) {
return null;
}
if (heap.size() == 1) {
return heap.remove(heap.size() - 1);
}
int root = heap.get(0);
heap.set(0, heap.remove(heap.size() - 1));
percolateDown(0);
return root;
}
private void percolateDown(int index) {
int size = heap.size();
while (index < size) {
int smallest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < size && heap.get(left) < heap.get(smallest)) {
smallest = left;
}
if (right < size && heap.get(right) < heap.get(smallest)) {
smallest = right;
}
if (smallest != index) {
swap(index, smallest);
index = smallest;
} else {
break;
}
}
}
private void swap(int i, int j) {
int temp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, temp);
}
// Example usage:
public static void main(String[] args) {
MinHeap minHeap = new MinHeap();
minHeap.insert(10);
minHeap.insert(4);
minHeap.insert(9);
minHeap.insert(2);
minHeap.insert(7);
System.out.println("Min element peek: " + minHeap.getMin()); // Output: 2
System.out.println("Min element: " + minHeap.remove()); // Output: 2
System.out.println("Min element: " + minHeap.remove()); // Output: 4
minHeap.insert(5);
System.out.println("Min element: " + minHeap.remove()); // Output: 5
}
}
Go
package main
import (
"fmt"
)
type MinHeap struct {
heap []int
}
func NewMinHeap() *MinHeap {
return &MinHeap{heap: []int{}}
}
func (h *MinHeap) IsEmpty() bool {
return len(h.heap) == 0
}
func (h *MinHeap) GetMin() int {
if h.IsEmpty() {
return -1 // Return -1 if the heap is empty (or handle appropriately)
}
return h.heap[0]
}
func (h *MinHeap) GetSize() int {
return len(h.heap)
}
func (h *MinHeap) Insert(value int) {
h.heap = append(h.heap, value)
h.percolateUp(len(h.heap) - 1)
}
func (h *MinHeap) percolateUp(index int) {
parentIndex := (index - 1) / 2
for index > 0 && h.heap[index] < h.heap[parentIndex] {
h.heap[index], h.heap[parentIndex] = h.heap[parentIndex], h.heap[index]
index = parentIndex
parentIndex = (index - 1) / 2
}
}
func (h *MinHeap) Remove() int {
if h.IsEmpty() {
return -1 // Return -1 if the heap is empty (or handle appropriately)
}
if len(h.heap) == 1 {
min := h.heap[0]
h.heap = h.heap[:0]
return min
}
root := h.heap[0]
h.heap[0] = h.heap[len(h.heap)-1]
h.heap = h.heap[:len(h.heap)-1]
h.percolateDown(0)
return root
}
func (h *MinHeap) percolateDown(index int) {
size := len(h.heap)
for index < size {
smallest := index
left := 2*index + 1
right := 2*index + 2
if left < size && h.heap[left] < h.heap[smallest] {
smallest = left
}
if right < size && h.heap[right] < h.heap[smallest] {
smallest = right
}
if smallest != index {
h.heap[index], h.heap[smallest] = h.heap[smallest], h.heap[index]
index = smallest
} else {
break
}
}
}
func main() {
minHeap := NewMinHeap()
minHeap.Insert(10)
minHeap.Insert(4)
minHeap.Insert(9)
minHeap.Insert(2)
minHeap.Insert(7)
fmt.Println("Min element peek:", minHeap.GetMin()) // Output: 2
fmt.Println("Min element:", minHeap.Remove()) // Output: 2
fmt.Println("Min element:", minHeap.Remove()) // Output: 4
minHeap.Insert(5)
fmt.Println("Min element:", minHeap.Remove()) // Output: 5
}
C++
#include <iostream>
#include <vector>
#include <stdexcept>
class MinHeap {
private:
std::vector<int> heap;
void percolateUp(int index) {
int parentIndex = (index - 1) / 2;
while (index > 0 && heap[index] < heap[parentIndex]) {
std::swap(heap[index], heap[parentIndex]);
index = parentIndex;
parentIndex = (index - 1) / 2;
}
}
void percolateDown(int index) {
int size = heap.size();
while (index < size) {
int smallest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < size && heap[left] < heap[smallest]) {
smallest = left;
}
if (right < size && heap[right] < heap[smallest]) {
smallest = right;
}
if (smallest != index) {
std::swap(heap[index], heap[smallest]);
index = smallest;
} else {
break;
}
}
}
public:
bool isEmpty() const {
return heap.empty();
}
int getMin() const {
if (isEmpty()) {
throw std::runtime_error("Heap is empty");
}
return heap.front();
}
int getSize() const {
return heap.size();
}
void insert(int value) {
heap.push_back(value);
percolateUp(heap.size() - 1);
}
int remove() {
if (isEmpty()) {
throw std::runtime_error("Heap is empty");
}
if (heap.size() == 1) {
int min = heap.front();
heap.pop_back();
return min;
}
int root = heap.front();
heap[0] = heap.back();
heap.pop_back();
percolateDown(0);
return root;
}
};
int main() {
MinHeap minHeap;
minHeap.insert(10);
minHeap.insert(4);
minHeap.insert(9);
minHeap.insert(2);
minHeap.insert(7);
std::cout << "Min element peek: " << minHeap.getMin() << std::endl; // Output: 2
std::cout << "Min element: " << minHeap.remove() << std::endl; // Output: 2
std::cout << "Min element: " << minHeap.remove() << std::endl; // Output: 4
minHeap.insert(5);
std::cout << "Min element: " << minHeap.remove() << std::endl; // Output: 5
return 0;
}
Rust
struct MinHeap {
heap: Vec<i32>,
}
impl MinHeap {
fn new() -> Self {
MinHeap { heap: Vec::new() }
}
fn is_empty(&self) -> bool {
self.heap.is_empty()
}
fn get_min(&self) -> Option<i32> {
if self.is_empty() {
None
} else {
Some(self.heap[0])
}
}
fn get_size(&self) -> usize {
self.heap.len()
}
fn insert(&mut self, value: i32) {
self.heap.push(value);
self.percolate_up(self.heap.len() - 1);
}
fn percolate_up(&mut self, mut index: usize) {
while index > 0 {
let parent_index = (index - 1) / 2;
if self.heap[index] < self.heap[parent_index] {
self.heap.swap(index, parent_index);
index = parent_index;
} else {
break;
}
}
}
fn remove(&mut self) -> Option<i32> {
if self.is_empty() {
return None;
}
if self.heap.len() == 1 {
return self.heap.pop();
}
let root = self.heap[0];
self.heap[0] = self.heap.pop().unwrap();
self.percolate_down(0);
Some(root)
}
fn percolate_down(&mut self, mut index: usize) {
let size = self.heap.len();
loop {
let left = 2 * index + 1;
let right = 2 * index + 2;
let mut smallest = index;
if left < size && self.heap[left] < self.heap[smallest] {
smallest = left;
}
if right < size && self.heap[right] < self.heap[smallest] {
smallest = right;
}
if smallest != index {
self.heap.swap(index, smallest);
index = smallest;
} else {
break;
}
}
}
}
fn main() {
let mut min_heap = MinHeap::new();
min_heap.insert(10);
min_heap.insert(4);
min_heap.insert(9);
min_heap.insert(2);
min_heap.insert(7);
println!("Min element peek: {:?}", min_heap.get_min()); // Output: Some(2)
println!("Min element: {:?}", min_heap.remove()); // Output: Some(2)
println!("Min element: {:?}", min_heap.remove()); // Output: Some(4)
min_heap.insert(5);
println!("Min element: {:?}", min_heap.remove()); // Output: Some(5)
}
Output
Min element peek: 2
Min element: 2
Min element: 4
Min element: 5
Using the heap push (insertion new element) we can create a heap if we are getting elements. In case we already have an array then we can convert it into a heap using Heapify method. We will discuss this later while learning about when and why to use Heapify.
| Operation | Worst Case |
|---|---|
| Get min | O(1) |
| Delete | O(log n) |
| Insert | O(log n) |
For full implementation to create heap from an array using heapify check this -
