Heaps

Last updated Nov 8, 2022 Edit Source

# Heaps

A specialized tree based data structure.

Efficient data structure to implement a priority queue.

# Implementations

Binary Heap built with a Binary Tree:

# Operations

# Fix Heap (maximising)

Method to obtain retain the heap structure after the root is removed. Assumes both left and right subtrees are already maximising heaps.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
fixHeap(H,k){
	if (H is a leaf)
		insert k in root of H;
	else {
		compare left and right child;
		largerSubHeap = the larger child of H;
		//key is the largest element
		if (k >= key of root(largerSubHeap))
			insert k in root of H;
		//key is not the largest, move the largest element up
		else{
			insert root(largerSubHeap) in root of H;
			//recursively find the spot where key is the largest
			fixHeap(largerSubHeap, k)
		}
	}
}