Priority Queue with Animation - Interactive Learning
Master Priority Queue - DSA Learning Platform ⭐ Master Priority Queue Priority-Based Heap Structure Learn Priority Queue with interactive heap visualizations - Insert, Extract, and Heapify operations! 📖 Understanding Priority Queue Introduction Heap Types Heapify Process Operations Applications What is a Priority Queue? A Priority Queue is an abstract data type where each element has a priority associated with it. Unlike a regular queue (FIFO), elements are served based on their priority level, not their arrival order. The most common implementation of a Priority Queue is using a Binary Heap, which provides efficient O(log n) operations for insertion and extraction. Priority Queues are essential in many algorithms including Dijkstra's shortest path, Huffman coding, A* search, and task scheduling. Key Difference: In a regular queue, "first come, first served". In a priority queue, "highest priority served first"! 🔑 Key Properties Each element has an associated priority Highest (or lowest) priority element is served first Typically implemented using Binary Heap O(log n) for insert and extract operations O(1) for peek (get highest priority) Complete binary tree structure Types of Heaps A Binary Heap is a complete binary tree that satisfies the heap property. There are two types: 📈 Max-Heap Parent node is always greater than or equal to its children parent ≥ children Root = Maximum element 📉 Min-Heap Parent node is always less than or equal to its children parent ≤ children Root = Minimum element 📐 Array Representation For a node at index i: Parent: (i - 1) / 2 Left Child: 2*i + 1 Right Child: 2*i + 2 📍 Heap Structure Max-Heap Example: [50] ← Root (Maximum) / \ [30] [20] / \ / \ [10] [15] [8] [5] Array: [50, 30, 20, 10, 15, 8, 5] 0 1 2 3 4 5 6 Min-Heap Example: [5] ← Root (Minimum) / \ [10] [8] / \ / \ [30] [15] [20] [50] Array: [5, 10, 8, 30, 15, 20, 50] The Heapify Process Heapify is the process of converting a binary tree into a heap or maintaining the heap property after insertion/deletion. ⬆️ Heapify Up (Bubble Up) Used after insertion. The new element is added at the end and "bubbles up" by swapping with its parent until the heap property is restored. ⬇️ Heapify Down (Bubble Down) Used after extraction. The last element replaces the root, then "bubbles down" by swapping with the appropriate child until heap property is restored. 🔄 Build Heap To build a heap from an array, heapify down starting from the last non-leaf node to the root. Time complexity: O(n) 📍 Heapify Up Example (Max-Heap) Insert 45 into heap [50, 30, 20, 10]: Step 1: Add at end [50] / \ [30] [20] / \ [10] [45] ← New element Step 2: Compare with parent (30) 45 > 30 → SWAP! [50] / \ [45] [20] / \ [10] [30] Step 3: Compare with parent (50) 45 < 50 → STOP! Heap property restored ✓ Priority Queue Operations 📥 Insert Add element, then heapify up to maintain heap property O(log n) 📤 Extract Max/Min Remove root, replace with last, heapify down O(log n) 👁️ Peek View the root (h...
Subject: Data Structures with Animation | Chapter: Priority Queue