Heaps are powerful data structures that maintain a specific order between parent and child nodes. They come in two flavors: min-heaps and max-heaps, each with unique properties that make them ideal for different applications.

Heaps support efficient insertion and deletion operations, both with O(log n) time complexity. Their array-based implementation allows for easy calculation of parent and child node indices, making them a popular choice for priority queues and sorting algorithms.

Heap Data Structure

Structure and properties of binary heaps

• Binary heap is a complete binary tree
  • All levels except possibly the last are fully filled with nodes
  • Nodes are filled from left to right in the last level
• Heap property maintains a specific ordering between parent and child nodes
  • Min-heap: Parent node is less than or equal to its children (root contains minimum value)
  • Max-heap: Parent node is greater than or equal to its children (root contains maximum value)
• No implied ordering exists between sibling nodes in a heap

Min-heaps vs max-heaps

• Min-heap organizes data with the smallest value at the root
  • Commonly used to implement priority queues where lowest priority elements are dequeued first (task scheduling)
• Max-heap organizes data with the largest value at the root
  • Commonly used to implement priority queues where highest priority elements are dequeued first (event handling)

Operations in heap data structures

• Insertion (heapify-up) adds a new element to the heap
  1. Add the new element to the end of the array representation
  2. Compare the new element with its parent node
  3. Swap the new element with its parent if the heap property is violated
  4. Repeat steps 2-3 until the heap property is satisfied or the root is reached
• Deletion (heapify-down) removes the root element from the heap
  1. Remove the root element and replace it with the last element in the array
  2. Compare the new root with its child nodes
  3. Swap the root with the smaller (min-heap) or larger (max-heap) child if the heap property is violated
  4. Repeat steps 2-3 until the heap property is satisfied or a leaf node is reached
• Peek returns the root element without modifying the heap structure

Time complexity of heap operations

• Insertion and deletion operations have a time complexity of $O(\log n)$
  • In the worst case, the new element may need to be swapped with its parent up to the root level (insertion)
  • In the worst case, the new root may need to be swapped with its child down to the leaf level (deletion)
• Peek operation has a time complexity of $O(1)$ as it only accesses the root element
• Building a heap from an array has a time complexity of $O(n)$
  • Heapify-down is called for each non-leaf node, which is more efficient than inserting elements one by one

Array-based implementation of heaps

• Nodes are stored in an array without the need for explicit pointers
• For a node at index $i$, its child and parent indices can be calculated:
  • Left child is at index $2i + 1$
  • Right child is at index $2i + 2$
  • Parent is at index $\lfloor(i - 1) / 2\rfloor$
• Array-based implementation allows for easy calculation of parent and child node indices

Heap Operations

Heapify-up (insertion)

1. Start at the newly inserted node at the end of the array
2. Compare the node with its parent node
3. If the heap property is violated, swap the node with its parent
4. Repeat steps 2-3 until the heap property is satisfied or the root is reached

Heapify-down (deletion)

1. Start at the root node after replacing it with the last element in the array
2. Compare the node with its smaller (min-heap) or larger (max-heap) child
3. If the heap property is violated, swap the node with the corresponding child
4. Repeat steps 2-3 until the heap property is satisfied or a leaf node is reached