Priority Queue / Heap

Priority Queue

A priority queue is an abstract data type similar to a regular queue or stack, but where each element has a priority associated with it. In a priority queue, elements are served based on their priority rather than just their order in the queue. The element with the highest (or lowest) priority is always removed first.

Key Operations

• Insert (enqueue): Add an element with a given priority.
• delete (dequeue): Remove and return the element with the highest priority.
• Peek: Return the element with the highest priority without removing it.

Priority queues are widely used in algorithms like Dijkstra's shortest path, A* search, Huffman coding, and in operating systems for task scheduling.

Heap

A heap is a specialized tree-based data structure that satisfies the heap property:

• In a max heap, for any given node, the value is greater than or equal to the values of its children.
• All leaves should be at h or h-1 levels, making it a complete binary tree

Heaps are commonly used to implement priority queues because they allow both insertion and deletion of the highest (or lowest) priority element in O(log n) time.

Types of Heaps

• Binary Heap: The most common heap implementation, where each node has at most two children.
• Fibonacci Heap: Supports faster amortized time for some operations, used in advanced algorithms.
• Binomial Heap: Useful for merging heaps efficiently.

Binary Heap

A binary heap is a complete binary tree that satisfies the heap property. It is usually implemented as an array, where for a node at index i:

• Left child is at 2i + 1
• Right child is at 2i + 2
• Parent is at (i - 1) // 2

Heapsort

Heapsort is a comparison-based sorting algorithm that uses a binary heap. It works as follows:

1. Build a max heap from the input data.
2. Swap the root (maximum value) with the last element.
3. Reduce the heap size by one and heapify the root.
4. Repeat until the heap is empty.

Heapsort has O(n log n) time complexity and is not stable, but it sorts in place.

Applications of Priority Queues

• Task Scheduling: Operating systems use priority queues to schedule tasks based on priority.
• Graph Algorithms: Dijkstra's and Prim's algorithms use priority queues to select the next node.
• Data Compression: Huffman coding uses priority queues to build optimal prefix codes.
• Simulation Systems: Event-driven simulations use priority queues to process events in order.

Implementation

class Heap {

    val heap: MutableList<Int> = mutableListOf() // Max Heap

    val size: Int
        get() = heap.size

    fun parent(val i: Int): Int {
        if (i < 0 || i >= heap.size)
            return -1
        return (i - 1) / 2
    }

    fun leftChild(val i: Int): Int {
        val l = 2 * i + 1
        if (i >= heap.size)
            return -1
        return l
    }

    fun rightChild(val i: Int): Int {
        val r = 2 * i + 2
        if (i >= heap.size)
            return -1
        return r
    }

    fun peek(): Int {
        if (heap.size == 0)
            return -1
        return heap[0]
    }

    fun heapify(val i: Int) {
        val l = leftChild(i)
        val r = rightChild(i)
        var max = if (l != -1 && heap[l] > heap[i]) l else i
        max = if (r != -1 && heap[r] > heap[max]) r else max
        if (max != i) {
            heap[i] = heap[max].also { heap[max] = heap[i] }
            heapify(max)
        }
    }

    fun delete() {
        if (heap.size == 0)
            return -1
        val data = heap[0]
        heap[0] = heap.last()
        heap.remove()
        heapify(0)
    }

    fun insert(val data: Int) {
        heap.add(data)
        var i = heap.size()
        var par = parent(i)
        while (i > 0 && data > heap[par]) {
            heap[i] = heap[par].also { heap[par] = heap[i] }
            i = par
            par = parent(i)
        }
    }
}

Fibonacci Heap

A Fibonacci Heap is a data structure consisting of a collection of min-heap-ordered trees. It supports a set of operations that are especially efficient for algorithms like Dijkstra's shortest path. The main advantage of a Fibonacci Heap is its excellent amortized time complexity for key operations such as insert, find-minimum, union, decrease-key, and delete-minimum.

Key Properties:

• Min-Heap Ordered: Each tree in the heap follows the min-heap property; the key of a parent is always less than or equal to its children.
• Collection of Trees: Unlike binary heaps, Fibonacci heaps are made up of a set of trees.
• Lazy Merging: Operations like union are performed lazily, which helps achieve better amortized time bounds.