အခန်း ၁၂ - Heap / Priority Queue

အရင်အခန်းတွေမှာ Queue (အခန်း ၇) ဆိုတာ "အရင်ဝင်တာ အရင်ထွက် (FIFO)" ဆိုတဲ့ စည်းမျဉ်းနဲ့ အလုပ်လုပ်တာ တွေ့ခဲ့ပါတယ်။ ဒါပေမယ့် real-world မှာ "အရင်ဝင်တာ အရင်ထွက်" မဟုတ်ဘဲ "အရေးကြီးဆုံးက အရင်ထွက်" ဖြစ်ရတဲ့ အခြေအနေတွေ အများကြီး ရှိပါတယ် —

• ဆေးရုံ အရေးပေါ်ခန်း (ER) မှာ အရင်ရောက်တဲ့ လူနာ မဟုတ်ဘဲ အခြေအနေ အဆိုးဆုံး လူနာကို အရင်ကုသည်။
• Operating system က job အများကြီးထဲက priority အမြင့်ဆုံး job ကို အရင် run သည်။
• Map app က လမ်းကြောင်းရှာတဲ့အခါ အနီးဆုံး/ကုန်ကျစရိတ် အနည်းဆုံး အရင် စစ်သည်။

ဒီလို "အရေးကြီးဆုံးကို အမြန် ထုတ်ယူ" ဖို့ အတွက် အကောင်းဆုံး data structure က Heap ဖြစ်ပြီး၊ သူ့ကို အသုံးပြုထားတဲ့ abstract concept ကို Priority Queue လို့ ခေါ်ပါတယ်။

ဒီအခန်းမှာ Heap ဆိုတာ ဘာလဲ၊ ဘာကြောင့် priority operation တွေမှာ မြန်သလဲ၊ ဘယ်အချိန်မှာ sorted array အစား Heap သုံးသင့်လဲ ဆိုတာတွေကို လေ့လာသွားပါမယ်။ ပြီးတော့ Heap ကို အသုံးချတဲ့ classic ပြဿနာ ၅ ခု — top K, kth largest, merge k lists, task scheduler, median stream — ကို တစ်ဆင့်ချင်း ဖြေရှင်းကြည့်ပါမယ်။

Priority Queue ဆိုတာ ဘာလဲ

Priority Queue ဆိုတာ element တစ်ခုစီမှာ priority (ဦးစားပေး အဆင့်) ပါပြီး၊ ထုတ်ယူတဲ့အခါ priority အမြင့်ဆုံး (သို့) အနိမ့်ဆုံး element ကို အရင် ထုတ်ပေးတဲ့ queue တစ်မျိုး ဖြစ်ပါတယ်။ သာမန် Queue နဲ့ ကွာတာက —

Priority Queue က interface (concept) ဖြစ်ပြီး၊ သူ့ကို အကောင်အထည်ဖော် (implement) ဖို့ နည်းလမ်း အများကြီး ရှိပါတယ်။ အကြမ်းဖျင်း နည်း ၃ မျိုး တွေးကြည့်ရအောင် —

Sorted array သုံးရင် ထုတ်ယူတာ မြန်ပေမယ့် (အမြဲ စီထားလို့)၊ element အသစ် ထည့်တိုင်း မှန်ကန်တဲ့ နေရာ ရှာ ထိုးထည့်ရလို့ $O(n)$ ကုန်ပါတယ်။ Heap က insert နဲ့ extract ၂ ခုလုံးကို $O(\log n)$ နဲ့ မျှတအောင် လုပ်ပေးတဲ့အတွက် insert/extract နှစ်ခုလုံး မကြာခဏ လုပ်ရတဲ့ workload အတွက် အကောင်းဆုံး ဖြစ်ပါတယ်။

မှတ်ချက်: Sorted Array မှာ priority အမြင့်ဆုံး/အနိမ့်ဆုံး item ကို array ရဲ့ နောက်ဆုံးဘက် မှာ ထားနိုင်ရင် extract က $O(1)$ ဖြစ်ပါတယ်။ ရှေ့ဘက်ကနေ remove လုပ်ရတဲ့ implementation မျိုးမှာတော့ ကျန် element တွေ ရွှေ့ ရလို့ $O(n)$ ဖြစ်နိုင်ပါတယ်။

Heap structure ကို နားလည်ခြင်း

Heap ဟာ စည်းမျဉ်း ၂ ခု ရှိတဲ့ binary tree (သားသမီး အများဆုံး ၂ ခုစီ ရှိတဲ့ tree) ဖြစ်ပါတယ် —

1. Heap Property (ဦးစားပေး စည်းမျဉ်း):

   • Min-Heap — မိဘ node က သားသမီး node ထက် ငယ် (သို့) တူ ရမည်။ ဒါကြောင့် အငယ်ဆုံး element က အမြဲ ထိပ် (root) မှာ ရှိသည်။
   • Max-Heap — မိဘ node က သားသမီး node ထက် ကြီး (သို့) တူ ရမည်။ ဒါကြောင့် အကြီးဆုံး element က အမြဲ ထိပ်မှာ ရှိသည်။

2. Complete Binary Tree (ပြည့်စုံ binary tree): အလွှာတိုင်းကို ဘယ်ကနေ ညာ အပြည့် ဖြည့်ထားရသည် (နောက်ဆုံး အလွှာသာ မပြည့်လည်း ရ၊ ဒါပေမယ့် ဘယ်ဘက်ကနေ စဖြည့်ရသည်)။

သတိ: Heap ဟာ Binary Search Tree (အခန်း ၁၄) မဟုတ်ပါ။ BST မှာ "ဘယ်ငယ်၊ ညာကြီး" ဆိုပြီး node အားလုံး အစီအစဉ်တကျ ရှိပေမယ့်၊ Heap မှာ မိဘ-သားသမီး ဆက်ဆံရေးကိုသာ ထိန်းသည်။ ဘေးချင်းကပ် (sibling) node တွေကြားမှာ အစီအစဉ် မရှိပါ။ ဒါကြောင့် Heap က "အငယ်ဆုံး/အကြီးဆုံး" ကိုသာ မြန်မြန် ပြောနိုင်ပြီး၊ "တန်ဖိုး x ရှိလား" ရှာဖို့တော့ မကောင်းပါ။

ဒီ Min-Heap ဥပမာကို ကြည့်ရအောင် — ထိပ်မှာ အငယ်ဆုံး 1 ရှိပြီး၊ မိဘတိုင်းက သားသမီးထက် ငယ်ပါတယ် —

graph TD
    N1((1)) --> N3((3))
    N1 --> N6((6))
    N3 --> N5((5))
    N3 --> N9((9))
    N6 --> N8((8))
    N6 --> N7((7))

1 = root (အငယ်ဆုံး)။ 1 < (3,6)၊ 3 < (5,9)၊ 6 < (8,7) → Min-Heap rule ပြည့်။

Array အဖြစ် သိမ်းခြင်း

Heap ရဲ့ အရေးကြီးဆုံး အချက်က — tree ပုံစံ ဖြစ်ပေမယ့် node, pointer တွေ မလိုဘဲ array သက်သက် နဲ့ သိမ်းနိုင်တာ ဖြစ်ပါတယ်။ Linked list (အခန်း ၈) နဲ့ tree တွေက node တစ်ခုစီမှာ "နောက် node ဘယ်မှာလဲ" ဆိုတဲ့ pointer (reference) သိမ်းရပါတယ်။ Heap မှာတော့ complete binary tree ဖြစ်လို့ နေရာ မလွတ် ဘဲ ဖြည့်ထားတဲ့အတွက်၊ node တစ်ခုစီကို array index တစ်ခုနဲ့ တစ်ပြိုင်နက် ချိတ်ဆက်နိုင်ပြီး pointer လုံးဝ မလိုတော့ပါ။

အပေါ်က tree ကို အလွှာလိုက် (level order — ဘယ်ကနေ ညာ) ဖတ်ပြီး array ထဲ ထည့်ကြည့်ရအောင် —

graph TD
    N0["1 (0)"] --> N1["3 (1)"]
    N0 --> N2["6 (2)"]
    N1 --> N3["5 (3)"]
    N1 --> N4["9 (4)"]
    N2 --> N5["8 (5)"]
    N2 --> N6["7 (6)"]

node label = တန်ဖိုး (index)။ array အဖြစ် ကြည့်ရင်:

index:   0   1   2   3   4   5   6
value: [ 1,  3,  6,  5,  9,  8,  7 ]

Index i ရှိ node တစ်ခုရဲ့ မိဘ နဲ့ သားသမီး တွေကို formula ၃ ခုနဲ့ တွက်ထုတ်နိုင်ပါတယ် —

  parent(i) = (i - 1) / 2     ← Parent (integer division — အကြွင်း ဖြုတ်)
  left(i)   = 2 * i + 1       ← left child
  right(i)  = 2 * i + 2       ← right child

သတိ: (i - 1) / 2 ဟာ integer division (Java မှာ Int အချင်းချင်း စားရင် အကြွင်း အလိုအလျောက် ဖြုတ်) ဖြစ်ပါတယ်။ ဥပမာ — index 2 ရဲ့ မိဘက (2 - 1) / 2 = 0 (0.5 မဟုတ်)၊ index 1 ရဲ့ မိဘကလည်း (1 - 1) / 2 = 0 ဖြစ်ပါတယ် — ဒါကြောင့် node 1, 2 ၂ ခုလုံးရဲ့ မိဘက root ဖြစ်တာ မှန်ကန်ပါတယ်။

ဒီ formula တွေ ဘယ်လို အလုပ်လုပ်လဲ ဥပမာနဲ့ စစ်ကြည့်ရအောင် —

ဥပမာ — index 2 (6) ရဲ့ left child က 2×2+1 = 5 (8)၊ right child က 2×2+2 = 6 (7)၊ မိဘက (2-1)/2 = 0 (1) ဖြစ်ပါတယ်။ tree ပုံနဲ့ တိုက်ကြည့်ရင် တိတိကျကျ ကိုက်ညီပါတယ်။ ဒီ index တွက်နည်းတွေက Heap Sort (အခန်း ၁၁) မှာ တွေ့ခဲ့တဲ့ heapify formula တွေ အတိအကျ ဖြစ်ပါတယ်။

ဘာကြောင့် ဒီ formula တွေ မှန်သလဲ? Complete binary tree မှာ node တွေကို အလွှာလိုက် ဆက်တိုက် ထည့်ထားလို့၊ index i ရဲ့ ရှေ့မှာ node i ခု ရှိပါတယ်။ Binary tree ဖြစ်လို့ node တစ်ခုစီမှာ child ၂ ခုစီ ရှိတဲ့အတွက်၊ index တွေဟာ ၂ ဆ ပုံစံ (2i+1, 2i+2) နဲ့ ဖြန့်သွားတာ ဖြစ်ပါတယ်။ ဒါကြောင့် node, pointer မလိုဘဲ သင်္ချာ တွက်ချက်မှု သက်သက်နဲ့ tree တစ်ခုလုံးကို ဖြတ်သန်းနိုင်တာ ဖြစ်ပါတယ်။

Heap ၏ အဓိက လုပ်ဆောင်ချက်များ

Heap မှာ အဓိက operation ၃ ခု ရှိပါတယ် — Peek, Insert, Extract။ Min-Heap ကို ဥပမာ ထားပြီး ကြည့်ရအောင်။

Peek — ထိပ်က element ကို ကြည့်ခြင်း ($O(1)$)

Heap ရဲ့ ထိပ် (root, index 0) မှာ အငယ်ဆုံး (Min-Heap) / အကြီးဆုံး (Max-Heap) က အမြဲ ရှိနေလို့၊ ဖတ်ဖို့ $O(1)$ သာ ကြာပါတယ်။ ဒါက Heap ရဲ့ အဓိက အားသာချက် ဖြစ်ပါတယ်။

Insert — element ထည့်ခြင်း ($O(\log n)$)

element အသစ်ကို ဘယ်နေရာ ထည့်ရင် —

• Heap property (Parent <= child) နဲ့
• Complete tree shape (နေရာ မလွတ်) —

၂ ခုလုံး မပျက်ဘဲ ဖြစ်မလဲ ဆိုတာ စဉ်းစားရပါတယ်။ ဖြေရှင်းချက်က ၂ ဆင့် —

1. နေရာချ: element အသစ်ကို array ရဲ့ နောက်ဆုံး (tree ရဲ့ နောက်ဆုံး အလွှာ၊ ဘယ်ဘက် နေရာလွတ်) မှာ အရင် ထည့်သည်။ ဒါက tree shape ကို မပျက်စေပါ။
2. sift up (အပေါ်တွန်းတင်): ဒါပေမယ့် အခု heap rule ပျက်နေနိုင်တယ် (element အသစ်က သူ့ parent ထက် ငယ်နေနိုင်တယ်)။ ဒါကြောင့် parent ထက် ငယ်နေသ၍ parent နဲ့ နေရာချင်း လဲတက် သွားသည် (bubble up)။ Parent ထက် မငယ်တော့ရင် (သို့) root ရောက်ရင် ရပ်သည်။

[1, 3, 6, 5, 9, 8] Min-Heap ထဲ 2 ထည့်ကြည့်ရအောင် —

Step 1 — နောက်ဆုံး (index 6) မှာ ထည့်:
            1
          /   \
         3     6
        / \   / \
       5   9 8   2     ← 2 ကို index 6 မှာ ထည့်
   array: [1, 3, 6, 5, 9, 8, 2]

Step 2 — sift up: 2 ရဲ့ parent = index (6-1)/2 = 2 (တန်ဖိုး 6)
         2 < 6 → လဲ
            1
          /   \
         3     2  ← 2 တက်လာ (index 2 ရောက်)
        / \   / \
       5   9 8   6
   array: [1, 3, 2, 5, 9, 8, 6]

Step 3 — 2 ရဲ့ parent = index (2-1)/2 = 0 (တန်ဖိုး 1)
         2 < 1? မဟုတ် → ရပ်
   ရလဒ်: [1, 3, 2, 5, 9, 8, 6]

element အသစ်က အများဆုံး root အထိ တက်နိုင်ပြီး၊ tree ရဲ့ အမြင့်က $\log n$ သာ ဖြစ်လို့ အဆိုးဆုံး $\log n$ ကြိမ်သာ လဲတက်ရပါတယ်။ ဒါကြောင့် $O(\log n)$ ဖြစ်ပါတယ်။

// Min-Heap ကို array (heap) နဲ့ size (count) ဖြင့် ကိုယ်တိုင် ရေးပြထားသည်
void insert(int[] heap, int[] size, int value) {
    int i = size[0];        // နောက်ဆုံး နေရာလွတ်
    heap[i] = value;        // Step 1: နောက်ဆုံးမှာ ထည့်
    size[0]++;

    // Step 2: sift up — မိဘထက် ငယ်နေသ၍ လဲတက်
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[i] < heap[parent]) {
            int temp = heap[i]; heap[i] = heap[parent]; heap[parent] = temp;
            i = parent;     // တက်သွားတဲ့ နေရာကနေ ဆက်စစ်
        } else {
            break;          // မိဘထက် မငယ်တော့ → ရပ်
        }
    }
}

Extract — ထိပ်က element ထုတ်ခြင်း ($O(\log n)$)

ထိပ် (root) ကို ထုတ်လိုက်ရင် root နေရာ ဟာသွားပါတယ်။ ဒါကို ဘယ်လို ပြန်ဖြည့်မလဲ? ထပ်ပြီး ၂ ဆင့် —

1. နောက်ဆုံးကို ထိပ်တင်: array ရဲ့ နောက်ဆုံး element ကို root နေရာ ရွှေ့တင်ပြီး၊ array အရွယ် ၁ လျှော့သည်။ ဒါက tree shape ကို မပျက်စေပါ (နောက်ဆုံး အလွှာက လျော့သွားရုံ)။
2. sift down (အောက်ဆင်းချ): အခု root က heap rule ပျက်နေနိုင်တယ် (root က child ထက် ကြီးနေနိုင်တယ်)။ ဒါကြောင့် child ၂ ခုထဲက ပိုငယ်တာထက် ကြီးနေသ၍ အဲ့ ပိုငယ်တဲ့ child နဲ့ လဲဆင်း ရသည်။ (Min-Heap မှာ ပိုငယ်တဲ့ child နဲ့ လဲမှ rule မပျက်ပါ။) children ထက် မကြီးတော့ရင် (သို့) leaf ရောက်ရင် ရပ်သည်။

Min-Heap [1, 3, 2, 5, 9, 8, 6] မှ root (1) ထုတ်:

Step 1 — root ထုတ်၊ နောက်ဆုံး (6) ကို ထိပ်တင်:
            6
          /   \
         3     2
        / \   /
       5   9 8
   array: [6, 3, 2, 5, 9, 8]

Step 2 — sift down: 6 ရဲ့ child = index 1 (3), index 2 (2)
         ပိုငယ်တာ = 2၊  2 < 6 → လဲ
            2
          /   \
         3     6  ← 6 ဆင်းသွား (index 2 ရောက်)
        / \   /
       5   9 8
   array: [2, 3, 6, 5, 9, 8]

Step 3 — 6 ရဲ့ child = index 5 (8) တစ်ခုသာ
         8 < 6? မဟုတ် → ရပ်
   ထုတ်လိုက်တာ: 1၊  ကျန် heap: [2, 3, 6, 5, 9, 8]

ဒီနေရာမှာလည်း root က အများဆုံး leaf အထိ ဆင်းနိုင်ပြီး tree အမြင့် $\log n$ သာ ဖြစ်လို့ $O(\log n)$ ဖြစ်ပါတယ်။

// Min-Heap မှ အငယ်ဆုံး (root) ကို ထုတ်ပြန်သည်
int extractMin(int[] heap, int[] size) {
    int min = heap[0];               // ထိပ် = အဖြေ
    size[0]--;
    heap[0] = heap[size[0]];         // Step 1: နောက်ဆုံးကို ထိပ်တင်

    // Step 2: sift down — child ထဲ ပိုငယ်တာထက် ကြီးနေသ၍ လဲ ဆင်း
    int i = 0;
    while (true) {
        int left = 2 * i + 1, right = 2 * i + 2, smallest = i;
        if (left < size[0] && heap[left] < heap[smallest]) smallest = left;
        if (right < size[0] && heap[right] < heap[smallest]) smallest = right;
        if (smallest == i) break;    // child ထက် မကြီးတော့ → ရပ်
        int temp = heap[i]; heap[i] = heap[smallest]; heap[smallest] = temp;
        i = smallest;                // ဆင်းသွားတဲ့ နေရာကနေ ဆက် စစ်
    }
    return min;
}

sift up နဲ့ sift down ကွာခြားချက်: sift up က element တစ်ခုကို parent တစ်ခုနဲ့သာ နှိုင်းယှဉ်ရလို့ ရိုးရှင်းသည်။ sift down က သားသမီး ၂ ခုနဲ့ နှိုင်းယှဉ်ပြီး ပိုငယ်တာ (Min-Heap) / ပိုကြီးတာ (Max-Heap) ကို ရွေး လဲရတဲ့အတွက် နည်းနည်း ပိုရှုပ်ပါတယ်။ ဒီ ၂ ခုက Heap operation အားလုံးရဲ့ အခြေခံ ဖြစ်ပါတယ်။ (shift up , shift down မဟုတ်ပါ။ Sift up , Sift down ဖြစ်ပါသည်။

အကျဉ်းချုပ်: Heap ဟာ Peek $O(1)$, Insert $O(\log n)$, Extract $O(\log n)$ ဖြစ်ပါတယ်။ ဒါက "အကြီးဆုံး/အငယ်ဆုံးကို မကြာခဏ ထုတ်၊ element အသစ် မကြာခဏ ထည့်" ဆိုတဲ့ workload အတွက် sorted array (insert $O(n)$) ထက် များစွာ ပိုကောင်းပါတယ်။

Build Heap — array တစ်ခုလုံးကို Heap ပြောင်းခြင်း ($O(n)$)

element တွေ အကုန် တစ်ပြိုင်နက် ရှိနေပြီးသား array တစ်ခုကို Heap ဖြစ်အောင် တည်ဆောက်ချင်ရင် — တစ်ခုချင်း insert ခေါ်ရင် $O(n \log n)$ ကုန်ပါတယ်။ ဒါပေမယ့် ပိုကောင်းတဲ့ နည်း ရှိပါတယ် — နောက်ဆုံး Parent node ကနေ စပြီး root အထိ၊ node တစ်ခုစီကို sift down လုပ်တာ ဖြစ်ပါတယ်။

void buildHeap(int[] arr) {
    int n = arr.length;
    // နောက်ဆုံး parent node = (n/2 - 1) ကနေ root (0) အထိ
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(arr, n, i);   // node i ကို အောက်ကို ချိန်ညှိ
    }
}

ဘာကြောင့် $O(n)$ ဖြစ်သလဲ ($O(n \log n)$ မဟုတ်)? node အများစုက tree ရဲ့ အောက်ခြေနားမှာ ရှိလို့ sift down က ၀ (သို့) ၁ အလွှာသာ ဆင်းရပါတယ် (leaf တွေက လုံးဝ မဆင်းရ)။ အပေါ်ပိုင်းက node နည်းနည်းသာ အလွှာများစွာ ဆင်းနိုင်ပါတယ်။ ဒါကြောင့် စုစုပေါင်း အလုပ်က $O(n \log n)$ မဟုတ်ဘဲ $O(n)$ ပဲ ဖြစ်ပါတယ်။ ဒါက Heap Sort (အခန်း ၁၁) ရဲ့ ပထမ အဆင့် (array → max-heap) ဖြစ်ပြီး၊ တစ်ခုချင်း insert လုပ်တာထက် ပိုမြန်ပါတယ်။

Heap vs Sorted Array — ဘယ်အချိန် ဘာသုံးမလဲ

Heap က အမြဲ အပြည့် စီထားတာ မဟုတ်ဘဲ၊ "အငယ်ဆုံး/အကြီးဆုံးက ထိပ်မှာ ရှိဖို့" လောက်ပဲ ထိန်းတာ ဖြစ်ပါတယ်။ ဒါက "ဘာကြောင့် insert မြန်သလဲ" ဆိုတဲ့ မေးခွန်းရဲ့ အဖြေ ဖြစ်ပါတယ် — အပြည့် မစီရတဲ့အတွက် အလုပ် နည်းပါတယ်။

ဥပမာ — element ၁ သန်းထဲက အကြီးဆုံး ၁၀ ခု ပဲ လိုချင်ရင်၊ အကုန် sort လုပ်ရင် $O(n \log n)$ ကုန်ပါတယ်။ ဒါပေမယ့် အရွယ် ၁၀ ရှိတဲ့ Heap သုံးရင် $O(n \log 10) \approx O(n)$ နဲ့ ရပါတယ် (နောက် "Top K" ပြဿနာမှာ ပြပါမယ်)။

Heap Sort နဲ့ ဆက်နွှယ်မှု: အခန်း ၁၁ မှာ တွေ့ခဲ့တဲ့ Heap Sort ဟာ ဒီ Heap structure ကိုပဲ အသုံးချတာ ဖြစ်ပါတယ် — element အားလုံးကို Heap ထဲ ထည့်ပြီး၊ ထိပ်ကနေ တစ်ခုချင်း ထုတ်ရင် စီပြီးသား အစီအစဉ် ရပါတယ်။ element n ခုကို extract လုပ်ရင် တစ်ခုစီ $O(\log n)$ ဖြစ်လို့ စုစုပေါင်း $O(n \log n)$ ဖြစ်ပါတယ်။ ဒါကြောင့် Heap ကို နားလည်ရင် Heap Sort ကိုပါ နားလည်ပြီး ဖြစ်ပါတယ်။

Programming Language ထဲက Priority Queue

လက်တွေ့မှာ Heap ကို ကိုယ်တိုင် ရေးစရာ မလိုပါ — language အများစုမှာ built-in ပါပြီးသား ဖြစ်ပါတယ်။ Java မှာ PriorityQueue က default အားဖြင့် Min-Heap ဖြစ်ပါတယ်။

import java.util.PriorityQueue;
import java.util.Collections;

class HeapDemo {
    void demo() {
        // Min-Heap (default): အငယ်ဆုံး အရင်ထွက်
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.offer(5);
        minHeap.offer(1);
        minHeap.offer(3);
        minHeap.peek();  // 1 (အငယ်ဆုံး၊ မထုတ်)
        minHeap.poll();  // 1 ထုတ် → ကျန် [3, 5]

        // Max-Heap: comparator ပြောင်းရန်
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.offer(5);
        maxHeap.offer(1);
        maxHeap.offer(3);
        maxHeap.peek();  // 5 (အကြီးဆုံး)
    }
}

မှတ်ချက်: Java PriorityQueue က default Min-Heap ဖြစ်တာ မှတ်ထားပါ။ Max-Heap လိုရင် Collections.reverseOrder() (သို့) custom Comparator ထည့်ရပါတယ်။ Object တွေအတွက်လည်း Comparator နဲ့ "ဘယ် field အလိုက် priority ပေးမလဲ" သတ်မှတ်နိုင်ပါတယ် (အခန်း ၁၁ က Custom Comparator အတိုင်း)။

Real-world Examples

Heap / Priority Queue ဟာ "အရေးကြီးဆုံးကို အရင်" ဆိုတဲ့ pattern ရှိတဲ့ system တိုင်းမှာ တွေ့ရပါတယ် —

• Job Queue — background job တွေကို priority အလိုက် run သည် (premium user ရဲ့ job ကို အရင်)။
• Retry Queue — fail သွားတဲ့ request တွေကို "နောက် retry လုပ်ရမယ့် အချိန် (timestamp)" အလိုက် Min-Heap ထဲ ထား၊ အချိန်ရောက်ဆုံးကို အရင် ထုတ် retry လုပ်သည်။
• Scheduler / Event Loop — OS scheduler နဲ့ timer system တွေက "နောက်ဆုံး အလုပ်လုပ်ရမယ့်အချိန်" အနီးဆုံး event ကို Min-Heap နဲ့ အရင် ထုတ်သည်။
• Notification Priority — notification တွေကို importance အလိုက် ပို့သည် (security alert ကို promotion ထက် အရင်)။
• Top Selling Products — sales stream ထဲကနေ "အရောင်းရဆုံး ၁၀ မျိုး" ကို Heap နဲ့ အမြဲ track လုပ်သည် (အကုန် sort မလုပ်ဘဲ)။
• Dijkstra's Algorithm (အခန်း ၁၉) — shortest path ရှာတဲ့အခါ "ကုန်ကျစရိတ် အနည်းဆုံး node" ကို Min-Heap နဲ့ အရင် ရွေးသည်။

ဒီ pattern တွေ အကုန်လုံးက တူညီပါတယ် — "item အများကြီးထဲက အရေးကြီးဆုံးကို မကြာခဏ ထုတ်၊ item အသစ်တွေ မကြာခဏ ဝင်လာ" ဆိုတဲ့ အခြေအနေပါ။ ဒီအချိန်မှာ Heap က အကောင်းဆုံး ဖြစ်ပါတယ်။

Questions

Heap / Priority Queue ကို လက်တွေ့ ပြဿနာ ၅ ခုနဲ့ ချိတ်ဆက် လေ့လာကြည့်ရအောင်။ မေးခွန်းတိုင်းရဲ့ သော့ချက်က — "ဘယ်အချိန်မှာ Min-Heap သုံးမလဲ၊ ဘယ်အချိန်မှာ Max-Heap သုံးမလဲ" ဆိုတာ မှန်ကန်စွာ ရွေးတတ်ဖို့ ဖြစ်ပါတယ်။

အောက်က ပြဿနာတွေမှာ Heap ကို သုံးရတဲ့ အကြောင်းရင်းက မတူပါဘူး။ တချို့က "အကြီးဆုံး k ခု ထိန်းထားဖို့" သုံးတာ၊ တချို့က "အချိန်တိုင်း အကြီးဆုံး/အငယ်ဆုံး ထုတ်ဖို့" သုံးတာ၊ တချို့က "အလယ်တန်ဖိုးကို ထိန်းဖို့" သုံးတာ ဖြစ်ပါတယ်။

၁။ Kth Largest Element in an Array

ကိန်းပြည့် array nums နဲ့ ကိန်း k ပေးထားသည်။ k ခုမြောက် အကြီးဆုံး (kth largest) element ကို ပြန်ပါ (စီပြီးသား အစီအစဉ်မှာ k နေရာမြောက်ကို ဆိုလိုသည်၊ distinct မဟုတ်)။

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Explanation: စီရင် [6,5,4,3,2,1] → ၂ ခုမြောက် အကြီးဆုံးက 5။

ရှင်းလင်းချက်

အလွယ်ဆုံး နည်းက အကုန် sort လုပ်ပြီး k နေရာမြောက် ယူတာ ဖြစ်ပေမယ့် $O(n \log n)$ ကုန်ပါတယ်။ ပိုကောင်းတဲ့ နည်းက အရွယ် k ရှိတဲ့ Min-Heap သုံးတာ ဖြစ်ပါတယ်။

အဓိက idea — "အကြီးဆုံး k ခု" ကို heap ထဲ ထားရင်၊ အဲ့ k ခုထဲက အငယ်ဆုံး (heap ထိပ်) က ကျွန်တော်တို့ လိုချင်တဲ့ kth largest ဖြစ်ပါတယ်။

• Min-Heap ထဲ element ထည့်သွားသည်။ heap အရွယ် k ထက် ကျော်ရင် ထိပ် (အငယ်ဆုံး) ကို ထုတ် ပစ်သည်။
• ဒါဆို heap ထဲမှာ "အကြီးဆုံး k ခု" သာ အမြဲ ကျန်ပြီး၊ ထိပ်က kth largest ဖြစ်သည်။

ဘာကြောင့် Max-Heap မဟုတ်ဘဲ Min-Heap သုံးသလဲ? "အကြီးဆုံး ၂ ခု" ထဲက မလိုတာ (ပိုသေးတာ) ကို ဖြုတ်ပစ်ဖို့၊ ထိပ်မှာ "အငယ်ဆုံး" ရှိတဲ့ Min-Heap က အဆင်ပြေပါတယ်။ Max-Heap သုံးရင် ထိပ်က အကြီးဆုံး ဖြစ်နေလို့ မလိုတာ ဖြုတ်ရ ခက်ပါတယ်။

Time Complexity: $O(n \log k)$ - element n ခုစီကို $O(\log k)$ heap operation လုပ်သောကြောင့်။ k သေးရင် $O(n \log n)$ ထက် မြန်သည်။
Space Complexity: $O(k)$ - heap မှာ element k ခုသာ ထား။

Java Solution

import java.util.PriorityQueue;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // Min-Heap: အကြီးဆုံး k ခုကိုသာ ထားသည်
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            // အရွယ် k ကျော်ရင် အငယ်ဆုံး (ထိပ်) ကို ဖြုတ်
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        // ကျန်တဲ့ k ခုထဲက အငယ်ဆုံး = kth largest
        return minHeap.peek();
    }
}

၂။ Top K Frequent Elements

ကိန်းပြည့် array nums နဲ့ ကိန်း k ပေးထားသည်။ Frequency အများဆုံး ဖြစ်တဲ့ element k ခုကို ပြန်ပါ။

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1, 2]
Explanation: 1 က ၃ ကြိမ်၊ 2 က ၂ ကြိမ်၊ 3 က ၁ ကြိမ်။ အများဆုံး ၂ ခုက [1, 2]။

ရှင်းလင်းချက်

ဒီပြဿနာကို အခန်း ၁၁ မှာ Bucket Sort idea နဲ့ $O(n)$ ဖြေခဲ့ပါတယ်။ ဒီနေရာမှာ Heap နဲ့ ဖြေပုံကို ကြည့်ရအောင် ($O(n \log k)$) — Top K pattern ကို လေ့ကျင့်ဖို့ ဖြစ်ပါတယ်။

• Step 1: Hash Map (အခန်း ၄) နဲ့ element တစ်ခုစီရဲ့ frequency ရေတွက်သည် — {1:3, 2:2, 3:1}။
• Step 2: frequency အလိုက် အရွယ် k Min-Heap ထဲ ထည့်သည်။ heap က k ကျော်ရင် frequency အနည်းဆုံးကို ဖြုတ်ပစ်သည်။
• Step 3: heap ထဲ ကျန်တဲ့ k ခုက "frequency အများဆုံး k ခု" ဖြစ်သည်။

ဒါက အရင်ပြဿနာ (Kth Largest) နဲ့ pattern တူပါတယ် — "frequency အကြီးဆုံး k ခု" ထားဖို့ Min-Heap သုံးတာ ဖြစ်ပါတယ်။

မှတ်ချက်: အဖြေ array ရဲ့ အစီအစဉ် မလိုပါ။ [1, 2] နဲ့ [2, 1] နှစ်ခုလုံး မှန်ပါတယ် (heap ကနေ ထုတ်တဲ့ အစီအစဉ်ပေါ် မူတည်)။

Time Complexity: $O(n \log k)$ - distinct element တစ်ခုစီကို $O(\log k)$ heap operation။
Space Complexity: $O(n + k)$ - map ($O(n)$) နှင့် heap ($O(k)$)။

Java Solution

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // Step 1: frequency ရေတွက်
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        // Step 2: frequency အလိုက် Min-Heap (frequency အနည်းဆုံး ထိပ်မှာ)
        // count.get(a) - count.get(b) သုံးရင် overflow ဖြစ်နိုင်လို့ Integer.compare သုံး
        PriorityQueue<Integer> heap = new PriorityQueue<>(
            (a, b) -> Integer.compare(count.get(a), count.get(b))
        );
        for (int num : count.keySet()) {
            heap.offer(num);
            if (heap.size() > k) {
                heap.poll();   // frequency အနည်းဆုံး ဖြုတ်
            }
        }

        // Step 3: heap ထဲ ကျန်တာ k ခုက အဖြေ
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = heap.poll();
        }
        return result;
    }
}

၃။ Merge k Sorted Lists

စီပြီးသား linked list k ခု ပါတဲ့ array ပေးထားသည်။ အကုန်လုံးကို တစ်ခုတည်း စီပြီးသား list အဖြစ် ပေါင်းပြီး ပြန်ပါ။

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

ရှင်းလင်းချက်

List k ခုစလုံး စီပြီးသား ဖြစ်လို့၊ "list တွေရဲ့ ရှေ့ဆုံး node k ခုထဲက အငယ်ဆုံးကို အရင် ထုတ်" ရင် ရပါတယ်။ ဒီ "အငယ်ဆုံးကို အမြန် ရှာ" ဆိုတဲ့ အလုပ်က Min-Heap ရဲ့ အလုပ်အတိအကျ ဖြစ်ပါတယ်။

• list k ခုရဲ့ ပထမ node k ခုကို Min-Heap ထဲ ထည့်သည်။
• heap ထိပ်က အငယ်ဆုံး node ကို ထုတ်ပြီး result list မှာ ဆက်သည်။
• ထုတ်လိုက်တဲ့ node ရဲ့ နောက် (next) node ကို heap ထဲ ပြန်ထည့်သည်။
• heap ဗလာ ဖြစ်တဲ့အထိ ထပ်လုပ်သည်။

heap ထဲမှာ အချိန်တိုင်း node k ခုသာ ရှိလို့၊ operation တစ်ခုစီ $O(\log k)$ ဖြစ်ပါတယ်။

ဘာကြောင့် Heap သုံးသလဲ? list k ခုရဲ့ ရှေ့ဆုံးတွေထဲက အငယ်ဆုံး ရှာဖို့ တစ်ခုချင်း နှိုင်းယှဉ်ရင် $O(k)$ ကုန်ပြီး၊ node N ခုအတွက် $O(N \times k)$ ဖြစ်ပါတယ်။ Heap သုံးရင် အငယ်ဆုံး ရှာတာ $O(\log k)$ ဖြစ်လို့ စုစုပေါင်း $O(N \log k)$ — k ကြီးရင် များစွာ ပိုမြန်ပါတယ်။

Time Complexity: $O(N \log k)$ - node စုစုပေါင်း N ခုစီကို $O(\log k)$ heap operation ($k$ = list အရေအတွက်)။
Space Complexity: $O(k)$ - heap မှာ node k ခုသာ။

Java Solution

import java.util.PriorityQueue;
import java.util.Comparator;

// ListNode အဖွဲ့အစည်း (အခန်း ၈ မှ)
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // Min-Heap: node ၏ val အလိုက် စီ
        // (a.val - b.val သုံးရင် ကိန်းကြီးတွေမှာ overflow ဖြစ်နိုင်လို့ comparingInt သုံး)
        PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));

        // list တစ်ခုစီ၏ ပထမ node ထည့်
        for (ListNode node : lists) {
            if (node != null) heap.offer(node);
        }

        ListNode dummy = new ListNode(0); // result ၏ ရှေ့ဆုံး အကူ node
        ListNode tail = dummy;

        while (!heap.isEmpty()) {
            ListNode smallest = heap.poll();   // အငယ်ဆုံး ထုတ်
            tail.next = smallest;              // result မှာ ဆက်
            tail = tail.next;
            // ထုတ်လိုက်တဲ့ node ၏ နောက် node ကို heap ထဲ ပြန်ထည့်
            if (smallest.next != null) {
                heap.offer(smallest.next);
            }
        }
        return dummy.next;
    }
}

၄။ Task Scheduler

CPU task တွေ (tasks, character A–Z) နဲ့ cooling time n ပေးထားသည်။ တူညီတဲ့ task ၂ ခုကြားမှာ အနည်းဆုံး n အလွတ် (interval) ရှိရမည်။ task အကုန် ပြီးဖို့ လိုအပ်တဲ့ အနည်းဆုံး interval အရေအတွက် ကို ပြန်ပါ။

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A → B → idle → A → B → idle → A → B  (interval ၈ ခု)
             တူညီ A ၂ ခုကြားမှာ အနည်းဆုံး ၂ အလွတ် ရှိရသည်။

ရှင်းလင်းချက်

အဓိက idea — frequency အများဆုံး task ကို အရင် လုပ် သင့်ပါတယ် (မဟုတ်ရင် နောက်ဆုံးမှာ အဲ့ task တွေ စုပြီး idle များစွာ ဖြစ်မယ်)။ "frequency အများဆုံးကို အမြန် ရွေး" ဖို့ Max-Heap သုံးပါတယ်။

• frequency ရေတွက်ပြီး Max-Heap ထဲ ထည့်သည်။
• interval n+1 အရွယ် တစ်ခုစီမှာ — heap ထိပ်ကနေ frequency အများဆုံး task တွေကို (အများဆုံး n+1 မျိုး) ထုတ် run သည်။
• run ပြီးတဲ့ task ရဲ့ frequency ကို ၁ လျှော့ပြီး၊ 0 မဟုတ်သေးရင် heap ထဲ ပြန်ထည့်သည်။
• heap ဗလာ ဖြစ်တဲ့အထိ ထပ်လုပ်ပြီး interval ရေတွက်သည်။

ဘာကြောင့် Max-Heap သုံးသလဲ? ဒီပြဿနာက "ကျန်နေသေးတဲ့ task တွေထဲ frequency အများဆုံးကို အရင် လုပ်" ဖို့ ဖြစ်လို့၊ ထိပ်မှာ အကြီးဆုံး ရှိတဲ့ Max-Heap က သင့်တော်ပါတယ်။ (အရင် ၃ ပြဿနာက "အကြီးဆုံး/အငယ်ဆုံး k ခု ထား" ဖို့ Min-Heap သုံးတာ — ဒီမှာတော့ "အကြီးဆုံးကို တိုက်ရိုက် ထုတ်သုံး" ဖို့ Max-Heap ဆိုတဲ့ ကွာခြားချက် သတိပြုပါ။)

Time Complexity: ဒီ simulation နည်းက cycle တစ်ခုစီမှာ idle slot အပါအဝင် n+1 slot ဖြတ်ရလို့ $O(\text{totalIntervals})$ ဖြစ်ပါတယ်။ task အမျိုးအစား ၂၆ မျိုးသာ ရှိလို့ heap operation က constant နီးပါး ဖြစ်သည်။ (သင်္ချာ formula နဲ့တွက်ရင် $O(N)$ နဲ့လည်း ရပေမယ့်၊ ဒီအခန်းအတွက် Heap simulation နည်းကို ပြထားတာ ဖြစ်ပါတယ်။)
Space Complexity: $O(1)$ - heap မှာ အများဆုံး ၂၆ မျိုးသာ။

Java Solution

import java.util.*;

class Solution {
    public int leastInterval(char[] tasks, int n) {
        // Step 1: frequency ရေတွက်
        int[] freq = new int[26];
        for (char t : tasks) freq[t - 'A']++;

        // Step 2: Max-Heap (frequency အများဆုံး ထိပ်)
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int f : freq) {
            if (f > 0) maxHeap.offer(f);
        }

        int intervals = 0;
        while (!maxHeap.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            int cycle = 0; // ဒီ cycle မှာ တကယ် run တဲ့ task အရေအတွက်
            // interval (n+1) တစ်ခုစီမှာ frequency အများဆုံး task တွေ ထုတ် run
            for (int i = 0; i < n + 1; i++) {
                if (!maxHeap.isEmpty()) {
                    int f = maxHeap.poll();
                    cycle++;
                    if (f - 1 > 0) temp.add(f - 1); // ၁ လျှော့ပြီး ကျန်ရင် မှတ်
                }
            }
            // run ပြီးသား task တွေ heap ထဲ ပြန်ထည့်
            for (int f : temp) maxHeap.offer(f);

            // heap ဗလာ ဖြစ်ရင် (နောက်ဆုံး cycle) တကယ် run တဲ့ အရေအတွက်သာ ပေါင်း (idle မရေတွက်)၊
            // မဖြစ်သေးရင် idle အပါအဝင် (n+1) လုံး ပေါင်း
            intervals += maxHeap.isEmpty() ? cycle : n + 1;
        }
        return intervals;
    }
}

၅။ Find Median from Data Stream

ကိန်းတွေ တစ်ခုပြီးတစ်ခု ဝင်လာ (stream) သည်။ အချိန်မရွေး လက်ရှိ ကိန်းအားလုံးရဲ့ median (အလယ်တန်ဖိုး) ကို ပြန်ပေးနိုင်တဲ့ data structure တည်ဆောက်ပါ။ (median = စီပြီးသား အလယ်တန်ဖိုး၊ အရေအတွက် စုံ ဖြစ်ရင် အလယ် ၂ ခုရဲ့ ပျမ်းမျှ)။

Example 1:

addNum(1)    →  [1]
addNum(2)    →  [1,2]
findMedian()  →  1.5   (1 နဲ့ 2 ၏ ပျမ်းမျှ)
addNum(3)    →  [1,2,3]
findMedian()  →  2     (အလယ်)

ရှင်းလင်းချက်

ကိန်းဝင်လာတိုင်း အကုန် sort လုပ်ရင် $O(n \log n)$ ကုန်ပါတယ်။ ပိုကောင်းတဲ့ နည်းက Heap ၂ ခု သုံးတာ ဖြစ်ပါတယ် — ဒါက Heap ရဲ့ classic technique တစ်ခု ဖြစ်ပါတယ်။

idea — ကိန်းတွေကို အလယ်မှာ ၂ ပိုင်း ခွဲ ထားသည် —

• Max-Heap (small) — အငယ်ပိုင်း (ဘယ်ခြမ်း) ကို သိမ်းသည်။ ထိပ်မှာ "ဘယ်ခြမ်းရဲ့ အကြီးဆုံး" ရှိသည်။
• Min-Heap (large) — အကြီးပိုင်း (ညာခြမ်း) ကို သိမ်းသည်။ ထိပ်မှာ "ညာခြမ်းရဲ့ အငယ်ဆုံး" ရှိသည်။

ဒီ ၂ ခုကို balance (အရေအတွက် ကွာတာ ၁ ထက် မပိုအောင်) ထိန်းထားရင် —

• median က heap ၂ ခုရဲ့ ထိပ် မှာ ရှိနေပါတယ်။ အရေအတွက် မညီရင် ပိုများတဲ့ heap ရဲ့ ထိပ်က median၊ ညီရင် ထိပ် ၂ ခုရဲ့ ပျမ်းမျှ ဖြစ်သည်။

ဒါကြောင့် addNum က $O(\log n)$၊ findMedian က $O(1)$ (ထိပ် ၂ ခု ဖတ်ရုံ) ဖြစ်ပါတယ်။

ဘာကြောင့် Heap ၂ ခု လိုသလဲ? Median ဆိုတာ "အလယ်" ဖြစ်လို့၊ ဘယ်ခြမ်းရဲ့ အကြီးဆုံး (Max-Heap) နဲ့ ညာခြမ်းရဲ့ အငယ်ဆုံး (Min-Heap) ၂ ခု သိရင် လုံလောက်ပါတယ်။ Heap ၂ ခုက အဲ့ "နယ်စပ် ၂ ဖက်" ကို $O(1)$ နဲ့ ပေးနိုင်လို့ အကောင်းဆုံး ဖြစ်ပါတယ်။

Time Complexity: addNum — $O(\log n)$၊ findMedian — $O(1)$။
Space Complexity: $O(n)$ - ကိန်းအားလုံး heap ၂ ခုထဲ သိမ်း။

Java Solution

import java.util.*;

class MedianFinder {
    private PriorityQueue<Integer> small; // Max-Heap: အငယ်ပိုင်း
    private PriorityQueue<Integer> large; // Min-Heap: အကြီးပိုင်း

    public MedianFinder() {
        small = new PriorityQueue<>(Collections.reverseOrder());
        large = new PriorityQueue<>();
    }

    public void addNum(int num) {
        small.offer(num);             // အရင် small ထဲ ထည့်
        large.offer(small.poll());    // small ၏ အကြီးဆုံးကို large သို့ ရွှေ့ (အစီအစဉ် မှန်အောင်)

        // balance: large က small ထက် များနေရင် ပြန်ညှိ
        if (large.size() > small.size()) {
            small.offer(large.poll());
        }
    }

    public double findMedian() {
        if (small.size() > large.size()) {
            return small.peek();      // အရေအတွက် မကိန်း — small ဘက် ပိုများ
        }
        // စုံ — ထိပ် ၂ ခု ပျမ်းမျှ ((double) cast အရင်လုပ်မှ int overflow မဖြစ်)
        return ((double) small.peek() + (double) large.peek()) / 2.0;
    }
}