Computer Science \ Data Structures \ Heaps

A heap is a specialized tree-based data structure that satisfies the heap property, which is used in computer science for priority queues and efficient sorting algorithms, among other applications. There are two main types of heaps: the max-heap and the min-heap. In a max-heap, for any given node \( i \), the value of \( i \) is greater than or equal to the values of its children. Conversely, in a min-heap, the value of \( i \) is less than or equal to the values of its children.

Structural Properties

1. Complete Binary Tree: Heaps are typically implemented as binary trees that are complete. This means that all levels, except possibly the last one, are fully filled, and all nodes are as far left as possible. This property ensures balanced tree height, making operations efficient.

2. Heap Property: Depending on whether it is a max-heap or a min-heap, the heap property must always be maintained. In a max-heap:
   \[
   A[parent(i)] \geq A[i]
   \]
   For a min-heap:
   \[
   A[parent(i)] \leq A[i]
   \]
   where \( A \) represents the array storing heap elements, and \( parent(i) \) is the parent node of \( i \).

Operations on Heaps

1. Insertion: To insert an element into a heap, the element is initially added at the end of the tree (maintaining the complete binary tree property) and then “bubbled up” (heapified) to restore the heap property. Steps:
   • Add the new element at the end.
   • Compare this element with its parent; if it violates the heap property, swap them.
   • Repeat the process until the heap property is restored.
2. Deletion (Extract-Max/Min): The root element (highest priority in max-heap or lowest in min-heap) is removed, and the last element in the heap replaces it. The new root is then “bubbled down” (heapified) to restore the heap property. Steps:
   • Replace the root with the last element.
   • Compare this element with its children; if it violates the heap property, swap it with the larger (max-heap) or smaller (min-heap) child.
   • Repeat the process until the heap property is restored.
3. Heapsort: This is an efficient comparison-based sorting algorithm that can be thought of in two phases:
   • Heap Creation: Transform the array into a heap.
   • Sorting: Repeatedly extract the maximum (or minimum) element from the heap and reconstruct the heap until it is empty. The heapsort algorithm has a time complexity of \( O(n \log n) \).

Applications of Heaps

1. Priority Queues: Heaps are widely used in implementing priority queues where elements are assigned a priority and the highest (or lowest) priority element is served first.
2. Median Maintenance: In dynamic data sets, two heaps are often used to keep track of the median element in real-time.

Given their efficiency in insertion, deletion, and access operations, heaps are foundational in computer science for implementing various algorithms and systems efficiently. Heaps combine the properties of ordering and structure, making them both practical and versatile in computational applications.