Heap နှင့် Priority Queue

နားလည်ထားရမယ့် အချက်

Priority queue ဆိုတာ abstract data type တစ်ခုပါ — insertion order ဘာပဲဖြစ်ဖြစ် priority အမြင့်ဆုံး item ကို ပထမဆုံးပေးပါတယ်။ Binary heap ကတော့ ဒါကို implement လုပ်တဲ့ standard concrete structure ဖြစ်ပြီး invariant တစ်ခုတည်း — heap property ပေါ်မှာ တည်ဆောက်ထားတယ်။ Min-heap တစ်ခုမှာ parent node တိုင်းရဲ့ value က child နှစ်ခုစလုံးထက် ငယ်တူညီရမယ်ဆိုတဲ့ property ပါ။ ဒါက full sorting ထက် weaker guarantee ဖြစ်တယ် (sibling တွေက ဘယ် order မဆို ဖြစ်နိုင်တယ်)၊ ဒီ weakness ကပဲ efficiency ရဲ့ source ဖြစ်တယ် — property ထိန်းသိမ်းဖို့ tree ပေါ်က local swap up/down ပဲလိုတယ်၊ global reorder မလိုဘူး။ Insert ကတော့ element အသစ်ကို append လုပ်ပြီး property ချိုးဖေါက်တဲ့ parent တွေကို ကျော်ဖြတ် 'bubble up' တက်သွားတယ် — tree height နဲ့ bound ထားတဲ့ O(log n) swap ပါ။ Extract-min ကတော့ root (အမြဲတမ်း minimum) ကို ဖယ်ရှား၊ last element ကို root နေရာသို့ ရွှေ့၊ ပြီးတော့ child တွေကျော်ဖြတ် 'sink down' ချသွားတယ် — ဒါလည်း O(log n)ပါ။ Peek-min ကတော့ root ကို ဖတ်ရုံသာဖြစ်လို့ O(1) ပါ။ Alternative တွေနဲ့ ယှဉ်ကြည့်ရအောင် — sorted list က O(1) find-min ပေးပေမယ့် O(n) insert (sort ဆက်ရှိအောင် element shift လုပ်ရလို့) ၊ unsorted list ကတော့ O(1) insert ပေမယ့် O(n) find-min (အားလုံး scan ရလို့) ဖြစ်တယ်။ Heap ကတော့ operation နှစ်ခုစလုံးမှာ log n ကုန်ကျစရိတ်ငယ်ငယ်လေးနဲ့ performance ကောင်းကောင်းရနိုင်တဲ့ practical middle ground ပါပဲ။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

Tutorial Platform ရဲ့ 'ဒီအပတ် trending' feature မှာ view count တွေ အမြဲ ပြောင်းလဲနေတဲ့ view အများဆုံး lesson တွေကို track လုပ်ထားပြီး view တိုင်းနောက် lesson catalog အားလုံးကို ပြန်ပြန် sort မလုပ်ဘဲ top အနည်းငယ်ကို efficient ဖြစ်စွာ ထုတ်ယူဖို့ လိုအပ်တယ်။ Size k fixed ထားတဲ့ min-heap (top k trending lesson တွေအထိ bound ထား) က ဒါကို ဈေးသက်သက်နဲ့ ဖြေရှင်းပေးတယ် — view-count update အသစ်ကို push လုပ်တာနဲ့ heap size k ကျော်ရင် rank အနိမ့်ဆုံးကို pop ချတာက O(log k) operation နှစ်ခုပါ၊ page load တိုင်းမှာ lesson ထောင်ချီကို ပြန် sort လုပ်တာထက် အများကြီးသက်သာတယ်။ ဒါက priority-queue pattern ကို လက်တွေ့ ကျင့်သုံးတဲ့ ပုံစံအဖြစ်ဆုံးပါပဲ — score အမြဲပြောင်းနေတဲ့အထဲက 'current top အနည်းငယ်' ကို score ပြောင်းတိုင်း full-sort cost မကုန်ဘဲ ရယူတာပါ။

• Heap property (min-heap): parent node က child နှစ်ခုစလုံးထက် ငယ်တူညီအမြဲတမ်းဖြစ်ရမယ်။
• Insert နဲ့ extract-min က O(log n) ဖြစ်ပြီး peek-min က O(1) ဖြစ်တယ်။
• Heap က sorted list (O(n) insert) နဲ့ unsorted list (O(n) find-min) ကြားက practical middle ground ဖြစ်တယ်။

အတူတူ စမ်းရေးကြည့်မယ်

import heapq

pq = []
heapq.heappush(pq, (3, "intro-to-loops"))
heapq.heappush(pq, (1, "critical-security-patch"))
heapq.heappush(pq, (2, "update-lesson-images"))

# heapq pops the smallest (priority, item) tuple first
while pq:
    priority, item = heapq.heappop(pq)
    print(priority, item)

Priority ငယ်စဉ် (1, 2, 3) အလိုက် 'critical-security-patch'၊ 'update-lesson-images'၊ 'intro-to-loops' ဆိုတဲ့ line သုံးကြောင်း print ထုတ်မည်။

Python Docs — heapq — Data Structures & Algorithms