Binary Heap Data Structure

Binary Tree

• Binary Tree → A hierarchical data structure in which each node has at most two children
• Binary trees can be classified into complete and incomplete binary trees based on their structural properties
• Complete Binary Trees
  • In a complete binary tree, all levels except possibly the last are completely filled, and all nodes are as far left as possible.
  • It is filled from top to bottom, left to right.
  • In a complete binary tree, if a node has a right child, it must also have a left child.
• Incomplete Binary Tree
  • In an incomplete binary tree, not all levels are completely filled, and nodes may not be as far left as possible.
  • It does not follow a strict pattern of filling nodes.

Binary Heap Data Structure

• A binary heap is a complete binary tree that satisfies the heap property (either min-heap or max-heap).
  • In a min-heap, each parent node has a value less than or equal to its children.
  • In a max-heap, each parent node has a value greater than or equal to its children.

Implementing Binary Heaps As Arrays

• The root node is array[0].
• For each parent node array[i], it children (if they exist) are elements array[2i+1] and array[2i+2].
• For the left and right child node array[i], its parent is at element array[(i-1)//2].
• An existing array can be converted into a heap in place in $O(n)$ time.
• A new item can be inserted into a binary heap in $O(log(n))$ time
• The maximum element can be removed from a binary heap in $O(log(n))$ time.

Binary Heap Operations

Rise → Move an element higher up the heap until it satisfies the heap property.

def rise(arr, i):
	parent = floor(i/2)
	while parent >= i:
		if array[parent] < array[i]:
			swap(array[parrent], array[i])
			i = parent
			parent = floor(i/2)

Fall → Move an element down the heap until it satisfies the heap property.

def fall(arr, i):
	child = 2i+1
	while child <= n:
		if child < n and array[child+1] > array[child]:
			child += 1
		if array[i] < array[child]:
			swap(array[i], array[child])
			i = child
			child = 2i

Heapify → Convert an unsorted array into a min/max heap

def heapify(arr):
	n = len(arr) - 1
	for I in range(n/2, 1, -1):
		fall(arr, i)

Insert → Insert an element into the heap.

def insert(arr, el):
	arr.append(el)
	rise(array, len(arr)-1)

Remove → Remove the min/max value from the heap

def extract_max(arr):
	swap(arr[0], arr[1])
	fall(arr, 0)
	return arr.pop()

Extra

In a binary heap, each parent has two children. The indexing formula (2i+1 for the left child and 2i+2 for the right child) comes from the way the binary heap is structured as a complete binary tree but represented in an array.

1. Starting Index: Arrays are zero-indexed, so starting from an index i for a parent node,
2. Left Child: The next layer of the tree (the children) starts at 2i + 1 because:
   • Doubling i (2i) shifts to the position at the start of the next level of a complete binary tree.
   • Adding 1 adjusts for the zero-based indexing, pointing to the first child (left).
3. Right Child: Similarly, for the right child at 2i + 2, you add one more to reach the second child’s position.

This arrangement helps in maintaining a compact, easily navigable tree structure within a simple array, allowing quick calculations to move between parent and child nodes.