Heap

A heap is a special tree-based data structure that satisfies specific properties, making it highly efficient for certain algorithms, such as priority queues. There are two main types of heaps: Min-Heaps and Max-Heaps.

Key Features of a Heap

1. Binary Tree Structure: Heaps are binary trees where each parent node has at most two child nodes.
2. Heap Property:
   • Min-Heap: The value of each parent node is less than or equal to the values of its child nodes. The smallest element is at the root.
   • Max-Heap: The value of each parent node is greater than or equal to the values of its child nodes. The largest element is at the root.

Use Cases

1. Priority Queues: Heaps are ideal for implementing priority queues, where the element with the highest priority (smallest or largest value) can be efficiently removed.
2. Heapsort: An efficient comparison-based sorting algorithm that uses heap properties.
3. Dijkstra’s Algorithm: Uses heaps to efficiently calculate the shortest paths in a graph.

Heap Operations

1. Insert: A new element is added to the end of the heap and then "percolated up" until the heap property is restored.
2. Remove Root: The root element is removed, and the last element in the heap is moved to the root and "percolated down" until the heap property is restored.
3. Peek: Returns the value at the root without removing it.

Example in PHP

Here is a simple example of implementing a Min-Heap in PHP:

class MinHeap {
    private $heap;

    public function __construct() {
        $this->heap = [];
    }

    public function insert($value) {
        $this->heap[] = $value;
        $this->percolateUp(count($this->heap) - 1);
    }

    public function extractMin() {
        if (count($this->heap) === 0) {
            return null; // Heap is empty
        }

        $min = $this->heap[0];
        $this->heap[0] = array_pop($this->heap);
        $this->percolateDown(0);

        return $min;
    }

    private function percolateUp($index) {
        while ($index > 0) {
            $parentIndex = intdiv($index - 1, 2);

            if ($this->heap[$index] >= $this->heap[$parentIndex]) {
                break;
            }

            $this->swap($index, $parentIndex);
            $index = $parentIndex;
        }
    }

    private function percolateDown($index) {
        $lastIndex = count($this->heap) - 1;

        while (true) {
            $leftChild = 2 * $index + 1;
            $rightChild = 2 * $index + 2;
            $smallest = $index;

            if ($leftChild <= $lastIndex && $this->heap[$leftChild] < $this->heap[$smallest]) {
                $smallest = $leftChild;
            }

            if ($rightChild <= $lastIndex && $this->heap[$rightChild] < $this->heap[$smallest]) {
                $smallest = $rightChild;
            }

            if ($smallest === $index) {
                break;
            }

            $this->swap($index, $smallest);
            $index = $smallest;
        }
    }

    private function swap($index1, $index2) {
        $temp = $this->heap[$index1];
        $this->heap[$index1] = $this->heap[$index2];
        $this->heap[$index2] = $temp;
    }
}

// Example usage
$heap = new MinHeap();
$heap->insert(5);
$heap->insert(3);
$heap->insert(8);
$heap->insert(1);

echo $heap->extractMin(); // Output: 1
echo $heap->extractMin(); // Output: 3
echo $heap->extractMin(); // Output: 5
echo $heap->extractMin(); // Output: 8

In this example, a Min-Heap is implemented where the smallest elements are extracted first. The insert and extractMin methods ensure that the heap properties are maintained after each operation.