ឧបករណ៍បង្ហាញ Binary Heap និង Priority Queue

Binary heap គឺជា complete binary tree ដែលមេ (parent) នីមួយៗមានតម្លៃតូចជាងកូនៗរបស់វា (min-heap) ឬធំជាង (max-heap) ដូច្នេះតម្លៃតូចបំផុត ឬធំបំផុតតែងតែស្ថិតនៅ root ជានិច្ច។ វាជាវិធីសាមញ្ញបំផុតសម្រាប់បង្កើត priority queue។ ឧបករណ៍នេះបង្ហាញ heap ជាទម្រង់ដើមឈើ និងជាទម្រង់ array នៅខាងក្រោមដែលរក្សាទុកទិន្នន័យជាក់ស្ដែង ដើម្បីឱ្យអ្នកឃើញថា index i មានកូននៅ index 2i + 1 និង 2i + 2។

បញ្ចូលតម្លៃមួយ ហើយមើលវា sift up ដោយប្ដូរវេនជាមួយ parent រហូតដល់ត្រូវតាមលក្ខខណ្ឌ heap។ ដកតម្លៃលើគេចេញ ហើយមើលតម្លៃចុងក្រោយផ្លាស់ទីទៅ root រួច sift down ចុះក្រោម។ បង្កើត heap ពី array ចៃដន្យដើម្បីមើលដំណើរការ heapify ពីក្រោមឡើងលើក្នុងល្បឿន O(n)។ node ដែលត្រូវប្ដូរវេនគ្នានឹងរំកិលទៅកន្លែងថ្មីយ៉ាងរលូន ងាយស្រួលតាមដានគ្រប់ជំហាន។

របៀបប្រើឧបករណ៍ ឧបករណ៍បង្ហាញ Binary Heap និង Priority Queue

1. ជ្រើសរើស Min-heap ឬ Max-heap។
2. វាយបញ្ចូលតម្លៃ រួចចុច Insert ឬចុច Extract min (ឬ max) ដើម្បីដក root ចេញ។
3. ចុច Build heap from random array ដើម្បីមើលការ heapify បំលែង array ដែលគ្មានលំដាប់ឱ្យទៅជា heap។
4. ប្រៀបធៀបដើមឈើ និង array៖ node ពណ៌ទឹកក្រូចកំពុងត្រូវបានប្រៀបធៀប រីឯ node ពណ៌ក្រហមកំពុងត្រូវបានប្ដូរវេនគ្នា។

ហេតុអ្វីប្រើ ឧបករណ៍បង្ហាញ Binary Heap និង Priority Queue របស់ ToolOrca

• ការបង្ហាញ heap ដូចគ្នាជាទម្រង់ដើមឈើ និង array
• ម៉ូដ Min-heap និង Max-heap
• បញ្ចូលទិន្នន័យដោយ sift up និងដកទិន្នន័យដោយ sift down
• បង្កើត heap ពីក្រោមឡើងលើ (heapify)
• ចលនាប្ដូរវេនគ្នាយ៉ាងរលូន និងមានឧបករណ៍រាប់ចំនួនលើកប្ដូរវេន
• កូដជាភាសា C++, Java, Python និង JavaScript

របៀបដែល binary heap ដំណើរការ

Heap គឺជា complete binary tree៖ គ្រប់កម្រិតសុទ្ធតែពេញ លើកលែងតែកម្រិតចុងក្រោយដែលអាចបំពេញពីឆ្វេងទៅស្ដាំ។ ទម្រង់បែបនេះអនុញ្ញាតឱ្យដើមឈើអាចរក្សាទុកក្នុង array ធម្មតាដោយមិនចាំបាច់ប្រើ pointer ឡើយ៖ root ស្ថិតនៅ index 0, កូនៗរបស់ index i ស្ថិតនៅ 2i + 1 និង 2i + 2 ហើយ parent របស់វាស្ថិតនៅ (i − 1) / 2 ដោយបង្គត់ចុះក្រោម។

លក្ខខណ្ឌ heap (heap property) កំណត់ថា parent នីមួយៗត្រូវតែ ≤ កូនៗរបស់វាក្នុង min-heap (≥ ក្នុង max-heap)។ វាមិនតម្រៀប array ទាំងមូលទេ វាគ្រាន់តែធានាថាតម្លៃនៅ root គឺតូចបំផុត (ឬធំបំផុត) ប៉ុណ្ណោះ។ វិធានការបន្ធូរបន្ថយនេះធ្វើឱ្យការកែប្រែទិន្នន័យចំណាយពេលតិច៖ កម្ពស់ដើមឈើគឺ log₂ n ដូច្នេះការ insert និង extract ចំណាយពេលត្រឹមតែ O(log n)។

ការ Insert, Extract និង Heapify

Insert: ដាក់តម្លៃថ្មីក្នុងប្រអប់ទទេបន្ទាប់នៅចុង array រួចធ្វើការ sift up៖ ដរាបណាតម្លៃនោះតូចជាង parent របស់វា (min-heap) ត្រូវប្ដូរវេនគ្នា។ Extract min: ដក root ចេញ រួចយកតម្លៃចុងក្រោយទៅដាក់នៅ root ហើយធ្វើការ sift down៖ ប្ដូរវេនវាជាមួយកូនដែលតូចជាង រហូតដល់គ្មានកូនណាដែលតូចជាងវាទៀត។

Build heap: ជំនួសឱ្យការ insert តម្លៃ n ម្តងមួយៗ (O(n log n)) យើងគ្រាន់តែ sift down គ្រប់ parent ចាប់ពីចុងក្រោយបង្អស់រហូតដល់ root។ node ភាគច្រើនស្ថិតនៅក្បែរបាតក្រោម និងផ្លាស់ទីតិចតួចបំផុត ដូច្នេះពេលសរុបគឺត្រឹមតែ O(n)។ Heap sort ប្រើវិធីនេះផ្ទាល់ រួចបន្តដោយការ extract ចំនួន n ដង។

កន្លែងដែលគេប្រើប្រាស់ Priority Queue

Priority queue ជ្រើសរើសទិន្នន័យណាដែលបន្ទាន់បំផុតមុនគេ៖ ដូចជានៅក្នុង Dijkstra’s shortest path និង Prim’s minimum spanning tree, ការកំណត់កាលវិភាគកិច្ចការ និងព្រឹត្តិការណ៍, A* search, ការច្របាច់បញ្ចូលគ្នានូវ k sorted lists, ការស្វែងរកតម្លៃធំជាងគេចំនួន k ក្នុង stream និង Huffman coding។ ប្រើប្រាស់ std::priority_queue ក្នុង C++, PriorityQueue ក្នុង Java និង heapq ក្នុង Python។

គ្រប់ visualizer នៅលើគេហទំព័រនេះដំណើរការផ្ទាល់ក្នុង browser របស់អ្នកជាមួយប៊ូតុងបញ្ជាដូចគ្នា៖ ចាក់ (Play), ផ្អាក (Pause), ទៅមុខមួយជំហាន, ថយក្រោយមួយជំហាន និងរបារលៃល្បឿន។ អ្នកក៏អាចអូសរបារកំណត់ទីតាំងដើម្បីលោតទៅជំហានណាមួយ ឬចុចលើផ្ទាំងគំនូរហើយប្រើប្រាស់ Space bar និងគ្រាប់ចុចព្រួញបានផងដែរ។