Heap ဆိုတာ ဘာလဲ? အရေးကြီးဆုံးအရာကို အရင်ထုတ်တဲ့ Data

လွယ်လွယ်ပြောရရင် Heap ဆိုတာ Data တွေကို အရေးကြီးတဲ့ အစဉ်အတိုင်း စီထားတဲ့ နည်းလမ်းပါ။ အရေးအကြီးဆုံးဟာက အမြဲတမ်း အပေါ်ဆုံးမှာ ရှိနေတယ်။ တစ်ခုယူပြီးတိုင်း နောက်အရေးကြီးဆုံးဟာက အလိုလို အပေါ်ကို တက်လာတယ်။ ရှာရတာ မြန်တယ်၊ ယူရတာ မြန်တယ်၊ ထည့်ရတာလည်း မြန်တယ်။

ကျွန်တော် ဒါကို ဆေးရုံရဲ့ Emergency အခန်းနဲ့ ဥပမာပေးချင်တယ်။ လူနာတွေ ဆေးရုံကို ရောက်လာတဲ့အခါ အရင်ရောက်တဲ့သူကို အရင်ကုသတာ မဟုတ်ပါဘူး။ ဆရာဝန်က အခြေအနေအဆိုးဆုံးသူကို အရင် ကုသပါတယ်။ နှလုံးဖောက်နေတဲ့သူက တုတ်ကွေးဖြစ်နေတဲ့သူထက် အရင်ကုသခံရမယ်။ အဆိုးဆုံးသူ ထွက်သွားပြီးရင် နောက်အဆိုးဆုံးသူက အလိုလို အရှေ့ဆုံးရောက်လာတယ်။ Heap လည်း အတူတူပါပဲ။ တန်းစီတဲ့အစဉ်က “အရင်လာသူ အရင်ရ” မဟုတ်ဘဲ “အရေးကြီးသူ အရင်ရ” ဖြစ်ပါတယ်။

Heap က ဘယ်လိုဖွဲ့စည်းထားတာလဲ?

Heap ကို များသောအားဖြင့် သစ်ပင်ပုံစံ (Binary Tree) နဲ့ တွေးပါတယ်။ ဒါပေမယ့် တကယ်သိမ်းထားတာက List ထဲမှာပါ။ သစ်ပင်ပုံက နားလည်ဖို့ လွယ်အောင် ဆွဲပြထားတာပါ။

Min-Heap ဆိုရင် အသေးဆုံးတန်ဖိုးက အပေါ်ဆုံးမှာ ရှိပါတယ်။ အောက်က အကိုင်းတိုင်းက အပေါ်က Node ထက် ကြီးရမယ်။ ဥပမာ အပေါ်ဆုံးက 1၊ အောက်မှာ 3 နဲ့ 5၊ သူတို့အောက်မှာ 8, 9, 12 ဆိုတာမျိုး။ Max-Heap ဆိုရင် ပြောင်းပြန်ပါ — အကြီးဆုံးတန်ဖိုးက အပေါ်ဆုံးမှာ ရှိတယ်။

စိတ်ဝင်စားစရာကောင်းတာက Heap ထဲမှာ Data တွေက အပြည့်အဝ အစဉ်လိုက် စီထားတာ မဟုတ်ပါဘူး။ 3 က 5 ထက် ဘယ်ဘက်မှာ ရှိရမယ်၊ ညာဘက်မှာ ရှိရမယ်ဆိုတာ အရေးမကြီးပါဘူး။ အရေးကြီးတာက အပေါ်ဆုံးမှာရှိတာက အသေးဆုံး (သို့) အကြီးဆုံး ဖြစ်နေဖို့ပဲ။ ဒါကြောင့် Heap ကို “တစ်ဝက်စီထားတဲ့” Data Structure လို့ ခေါ်လို့ရပါတယ်။ အပေါ်ဆုံးတစ်ခုကိုပဲ တိတိကျကျ သိရပြီး ကျန်တာတွေက ခန့်မှန်းခြေပဲ စီထားတာပါ။

Python မှာ Heap ကို ဘယ်လိုသုံးလဲ?

Python မှာ heapq ဆိုတဲ့ Module ပါပြီးသားပါ။ List သာမန်တစ်ခုကို Heap အဖြစ် ပြောင်းပြီး သုံးလို့ရပါတယ်။


import heapq

tasks = [5, 1, 4, 2, 3]
heapq.heapify(tasks)   # List ကို Heap အဖြစ် ပြောင်းတယ်
print(tasks)           # [1, 2, 4, 5, 3] — အသေးဆုံးက အရှေ့ဆုံး

heapq.heappush(tasks, 0)   # 0 ကို ထည့်တယ်
print(heapq.heappop(tasks))  # 0 ကို ထုတ်တယ် — အသေးဆုံးကို အရင်ထုတ်တယ်
print(heapq.heappop(tasks))  # 1 ကို ထုတ်တယ်

ဒီ Code လေးကို ကြည့်ရင် Heap ရဲ့ အဓိကအလုပ်သုံးခုကို တွေ့နိုင်ပါတယ်။

heappush — Data အသစ်ထည့်တာ။ ထည့်ပြီးရင် သူ့ထက်ကြီးတဲ့ အရာတွေရဲ့ အောက်ကို အလိုလို ရွေ့သွားပါတယ်။
heappop — အပေါ်ဆုံးက အသေးဆုံး (သို့) အကြီးဆုံး တန်ဖိုးကို ထုတ်တာ။ ထုတ်ပြီးရင် နောက်အသေးဆုံးက အလိုလို အပေါ်တက်လာပါတယ်။
heapify — List သာမန်တစ်ခုကို Heap အဖြစ် ပြောင်းတာ။

ဒီအလုပ်သုံးခုလုံးက မြန်ပါတယ်။ ထည့်တာ၊ ထုတ်တာက O(log n) ပါ။ Data သန်းချီရှိရင်တောင် အချိန်သိပ်မကြာပါဘူး။ အပေါ်ဆုံးကို ကြည့်ရုံကတော့ O(1) ပါ — ချက်ချင်း သိနိုင်ပါတယ်။

Heap ကို ဘယ်နေရာတွေမှာ သုံးလဲ?

Heap ကို နေ့စဉ်သုံးနေတဲ့ Software တွေထဲမှာ အများကြီး သုံးထားပါတယ်။

Task Scheduler — ကွန်ပျူတာက အလုပ်တွေကို အရေးကြီးတဲ့ အစဉ်အတိုင်း လုပ်ဖို့ Heap ကို သုံးပါတယ်။ အရေးကြီးတဲ့ အလုပ်ကို အရင်လုပ်တယ်။
Dijkstra Algorithm — မြေပုံပေါ်မှာ အတိုဆုံး လမ်းရှာတဲ့အခါ Heap ကို သုံးပြီး အနီးဆုံးနေရာကို အရင်ရွေးပါတယ်။ Google Maps နောက်ကွယ်မှာ ဒီလိုနည်းတွေ ရှိပါတယ်။
Top-K ရှာတာ — “အကြီးဆုံး 10 ခု” ဒါမှမဟုတ် “အရောင်းအကောင်းဆုံး 5 ခု” လို့ ရှာတဲ့အခါ Heap က အမြန်ဆုံးနည်းလမ်းပါ။ Data အားလုံးကို စီစရာမလိုဘဲ အပေါ်ဆုံးလေးတွေပဲ ထုတ်ယူလို့ရပါတယ်။
Event Simulation — ဂိမ်းထဲမှာ ဖြစ်ပျက်မယ့် အဖြစ်အပျက်တွေကို အချိန်အစဉ်အတိုင်း စီဖို့ Heap ကို သုံးပါတယ်။

Heap နဲ့ Sorted List ဘာကွာလဲ?

“အစဉ်လိုက် စီထားချင်ရင် List ကို sort လုပ်လိုက်ရုံပဲ မဟုတ်ဘူးလား?” လို့ မေးနိုင်ပါတယ်။ ကွာခြားချက်က Data အသစ်ဝင်လာတိုင်း ဘာဖြစ်မလဲဆိုတာပါ။ Sorted List မှာ Data အသစ်တစ်ခု ထည့်တိုင်း နေရာမှန်ကို ရှာပြီး အကုန်ရွှေ့ရပါတယ်။ Data များရင် နှေးပါတယ်။ Heap မှာတော့ Data အသစ်က သူ့နေရာကို အလိုလို ရှာသွားပြီး အပေါ်ဆုံးတစ်ခုကိုပဲ အစဉ်လိုက် ထိန်းထားပါတယ်။ ကျန်တာတွေကို အပြည့်အဝ မစီထားဘူး။ ဒါကြောင့် Heap က “အပေါ်ဆုံးတစ်ခုပဲ အရေးကြီးတယ်” ဆိုတဲ့ အလုပ်တွေမှာ ပိုမြန်ပါတယ်။

ဒါပေမယ့် Heap က အရာအားလုံးကို မစီထားတာမို့ “ဒုတိယအကြီးဆုံးက ဘာလဲ?” လို့ မေးရင် ချက်ချင်းမဖြေနိုင်ပါဘူး။ အပေါ်ဆုံးတစ်ခုကိုပဲ သေချာသိရတယ်။ အဲဒါက Heap ရဲ့ ကန့်သတ်ချက်ပါ။ အရာအားလုံးကို အစဉ်လိုက် သိချင်ရင် sort လုပ်ရပါမယ်။

Stack, Queue နဲ့ ဘာကွာလဲ?

အရင်က ဆောင်းပါးတွေမှာ Stack နဲ့ Queue အကြောင်း ပြောပြီးသားပါ။ Stack က “နောက်ဆုံးထည့်တာ အရင်ထွက်” (LIFO)၊ Queue က “အရင်ထည့်တာ အရင်ထွက်” (FIFO) ပါ။ Heap ကတော့ “အရေးကြီးတာ အရင်ထွက်” ပါ။ သုံးခုလုံးက Data ကို စီတဲ့နည်းတွေ ချည်းပါပဲ။ ကွာတာက ဘယ်အစဉ်အတိုင်း ထုတ်မလဲဆိုတာပါ။ ပြဿနာပေါ် မူတည်ပြီး မှန်တဲ့ Data Structure ကို ရွေးတတ်ဖို့က Programmer တစ်ယောက်ရဲ့ အရေးကြီးဆုံး အတတ်ပညာတွေထဲက တစ်ခုပါ။

Heap ဆိုတာ နာမည်ကြီးတဲ့ Data Structure တွေထဲမှာ နောက်ဆုံးမှ သင်ရလေ့ရှိတဲ့ တစ်ခုပါ။ ဒါပေမယ့် နားလည်သွားရင် “အော် ဒါကြောင့် ကွန်ပျူတာက အရေးကြီးတဲ့အလုပ်ကို အရင်လုပ်တာကိုး” လို့ သဘောပေါက်သွားမှာပါ။ 🙂

—