Heap

A heap is a special tree-based data structure that adheres to the properties of a heap (in a min-heap, the parent is always less than or equal to the child).

Priority Queue ADT is primarily implemented using a heap, and heaps are typically implemented as arrays. Consequently, a priority queue ends up being implemented as an array.

Notably, since heaps are complete binary trees, they are suitable for sequential representation in arrays. Therefore, binary heaps, which are in the form of complete binary trees, can be seamlessly positioned in arrays. Often, to simplify calculations, tree representations in arrays start indexing from 1.

Due to its characteristic of always maintaining balance, heaps are not only utilized in priority queues but also in algorithms such as Dijkstra's. They are also used in their original purpose of heap sort, implementing the Prim's algorithm for minimum spanning trees, and even for quickly approximating medians.

• Heaps define only parent-child relationships and not left-right relationships; hence they are not a sorted structure.

• A Binary Heap is a heap with two children, and it is the most commonly used form of a heap.

Heap Operation

class BinaryHeap(object):
    def __init__(self):
        self.items = [None] # index: 1
    
    def __len__(self):
        return len(self.items) - 1
    
    def _percolate_up(self):
        i = len(self)
        parent = i // 2
        while parent > 0:
            if self.items[i] < self.items[parent]:
                self.items[parent], self.items[i] = self.items[i], self.items[parent]
            i = parent
            parent = i // 2
    
    # heapq.heappush()
    def insert(self, k):
        self.items.append(k)
        self._percolate_up()
        
    def _percolate_down(self, idx):
        left = idx * 2
        right = idx * 2 + 1
        smallest = idx
        
        if left <= len(self) and self.items[left] < self.items[smallest]:
            smallest = left
        
        if right <= len(self) and self.items[right] < self.items[smallest]:
            smallest = right
        
        if smallest != idx:
            self.items[idx], self.items[smallest] = self.items[smallest], self.items[idx]
            self._percolate_down(smallest)
    
    # heapq.heappop()
    def extract(self):
        extracted = self.items[len(self)]
        self.item[1] = self.items[len(self)]
        self.items.pop()
        self._percolate_down(1)
        return extracted

Insertion

1. Insert the element at the most bottom level, as far left as possible. (If represented as an array, append it at the end).

2. Compare with the parent value; if it's smaller, swap their positions.

3. Continue this comparison and swapping with the parent value (it may rise up to the root if it's the smallest).

The _percolate_up() function, which reduces the parent to about half with i // 2, thus has a time complexity of $O(logn)$.

Extraction

Extracting the root has a time complexity of $O(1)$. However, after extraction, a procedure is required to maintain the heap properties, so the overall time complexity becomes $O(logn)$.

Binary Heap vs. Binary Search Tree

Binary Heap

Heaps ensure vertical relationships, especially in a min-heap, the parent is always less than its children. Therefore, if you need to extract the largest (max heap) or smallest value (min heap), you should use a binary heap. Extraction in a binary heap is achievable in $O(1)$.

Binary Search Tree

On the other hand, BSTs ensure horizontal relationships. In a BST, the parent is larger than its left child but smaller or equal to its right child. As a result, both search and insertion are achievable in $O(logn)$ with a BST. It is used when all values need to be sorted.