Heap

Abstract data type:

• ADT - Binary Tree
• ADT - Priority Queue

Data_StructureBinary_TreeHeap

---

Heap is a type of binary tree data structure, specifically, it is a complete binary tree with two main variants: the max-heap and the min-heap. The max-heap and min-heap make sure that their root node contains the maximum or minimum value, and the value decrease or increase as you move down the tree.

Properties

• A heap can store duplicate values
• Complete binary tree
  • A heap is a complete binary tree, meaning all levels of the tree are fully filled except possibly for the last level, which is filled from the left to right. This property ensures efficient storage of elements using arrays
• Heap order
  • In heap we don’t care about wether the left child is less than right child
  • In a max-heap, the maximum element is at the root, the value of the node is greater than or equal to the values of its children (if any)
  • In a min-heap, the minim element is at the root, the value of the node is less than or equal to the values of its children
• Parent-child relationship in array
  • In a heap represented as an array, if the element at index i represents a node, then
    • The left child of the node is a index 2i + 1
    • The right child of the node is a at index 2i + 2
    • The parent of the node is at index of (i-1)/2

Pros and cons

• Advantage
  • Guaranteed access to the maximum or minimum element: in a heap the root node is always the maximum or minimum element based on what variant of the heap it is
  • Efficient insertion and deletion: when an element is added to the heap, the heapify operation takes an average $O(\log n)$ time
  • Efficient priority queue: the heap data structure is commonly used to implement a priority queue, where the highest priority element is always at the top of the heap. The heap allows constant-time access to the highest priority element
• Disadvantage
  • Not ideal for searching: searching for an element in a heap requires traversing the entire tree, because there is no inherent ordering relationship between sibling nodes unlike BST.

Implementation

The implementation of a heap is typically using array, because adding elements in a heap is always added to the right most element in the last level of the tree structure, and there cannot be any gaps in the heap (it has to be a complete binary tree), and array is suitable in this scenario than using nodes. (find out more on array representation of binary tree: Sequential representation)

In the following example, we are implementing a max-heap.

public class MaxHeap {
	private int[] heap; // represent the heap in array
	private int size;
	private int capacity;
	
	public MaxHeap(int capacity) {
		this.capacity = capacity;
		this.size = 0; // initially size 0
		this.heap = new int[capacity];
	}
 
	// param: index of a node
	// return: index of its parent node
	private int parent(int idx) {
		return (idx - 1) / 2;
	}
 
	// param: index of a node
	// return: index of its left child node
	private int leftChild(int idx) {
		return 2 * idx + 1;
	}
	
	// param: index of a node
	// return: index of its right child node
	private int rightChild(int idx) {
		reutrn 2 * idx + 2;
	}
	
	// swap the element i and the element j in the heap array
	private void swap(int i, int j) {
		int temp = heap[i];
		heap[i] = heap[j];
		heapp[j] = temp;
	}
}

Insertion

When inserting element, the element is inserted at the end of the array, not the root node. When a node is inserted at the end of the array, we have to compare the node with its parent recursively and swap positions if necessary to preserve the heap property.

1. Insert the element into the heap, place at the end of the array
2. Compare the value of inserted element with its parent’s value
3. If the value of the newly inserted element is greater than its parent’s value, we swap the element with its parent
4. Repeat step 2 and 3 (swapping and comparing) until either the element’s value is no longer greater than its parent’s value, OR we reach the root of the heap (index 0)

public void insert(int value) {
	if (size >= capacity) {
		throw new IllegalStateException("Heap Overflow: Cannot insert element, heap is full");
	}
	
	heap[size] = value; // insert the element at the end of the array
	size++;
	heapifyUp(size-1); // heapify up from the newly inserted element 
}
 
public void heapifyUp(int idx) {
	// while the index of the new element is not reach the root AND
	// the new element is not less than its parent
	while (idx > 0 && heap[parent(idx)] < heap[idx]) {
		swap(i, parent(i));
		
		// update the idx to its parent's after swap
		// so in the next iteration the current position of the new element 
		// is updated
		idx = parent(idx);
	}
}

Deletion

The deletion method deletes and returns the root which is the maximum element.

1. Remove the root, store it in a variable for later return value
2. Replace the last element with the root, reduce the heap size
3. Recursively heapify down from root node, until the current node reaches a leaf, or the heap property is restored (the current node is greater than or equal to both its children, in a max-heap)
4. In the heapify down method, if a child is larger than the current node, swap the current node with that child.

public int deleteMax() {
	if (size == 0) {
		throw new IllegalStateException("Heap is empty");
	}
	int max = heap[0];
	heap[0] = heap[size-1]; // move the last element to the root
	size--; // ignores the last element (delete last element)
	heapifyDown()
	return max;
}
public void heapifyDown(int idx) {
	int largest = idx;
	int left = leftChild(idx);
	int right = rightChild(idx);
	
	// check if leaf is reached, or any child is larger than the current node
	// if the left child is not the last element AND it's larger than 
	// the current largest
	if (left < size && heap[left] > heap[largest]) {
		largest = left;
	}
	
	// if right child is larger than the current largest 
	if (right < size && heap[right] > heap[largest]) {
		largest = right;
	}
	
	// if the largest is not the root, swap with the largest and continue
	// heapify down
	if (largest != idx) {
		swap(idx, largest);
		heapifyDown(largest);
	}
}

Time complexity

• Insertion:$O(\log n)$
  • The insertion performs heapify up operation to maintain the heap property. The worst case time complexity of inserting an element is O$(\log n)$, which heapify up starts from the bottom to top, traverses the entire hight of the binary tree.
• Deletion: $O(\log n)$
  • When removing the root element (or any element) from the heap, the heapify down operation is performed to maintain the heap property. The worst case is when the root element is removed, the last element in the heap is moved to the root position, the heapify down is performed on the new root, the process is repeated in a top-down manner. The worst case complexity is $O(\log n)$ for traversing the entire height of the binary tree.
• Peek: $O(1)$
  • Retrieving the minimum or maximum from the heap takes constant time, as the element is always located at the root.

---

Back to parent node: ADT - Binary Tree