Heap sort ប្រើ binary heap ដែលរក្សាទុកក្នុង array ផ្ទាល់។ ដំបូងវាផ្លាស់ប្តូរ array ទៅជា max-heap ដែល parent នីមួយៗមានតម្លៃយ៉ាងហោចណាស់ស្មើ ឬធំជាង child របស់វា ដូច្នេះតម្លៃធំបំផុតស្ថិតនៅ index 0។ បន្ទាប់មកវា swap តម្លៃនោះទៅខាងចុង array បន្ថយទំហំ heap មួយ និង sift ចុះក្រោមដើម្បីជួសជុល heap ដោយធ្វើដដែលៗរហូតដល់ heap អស់ធាតុ។
ឧបករណ៍បង្ហាញនេះបង្ហាញ parent នីមួយៗ (ពណ៌ស្វាយ) ត្រូវបានប្រៀបធៀបជាមួយ children (ពណ៌ទឹកក្រូច) និងការ swap ពណ៌ក្រហម ខណៈដែលផ្នែកកន្ទុយដែលតម្រៀបរួចកើនឡើងជាពណ៌បៃតងពីខាងស្តាំ។ ដើម្បីមើល heap គូរជាដើមឈើ សូមបើក binary heap visualizer។
របៀបប្រើឧបករណ៍ កម្មវិធីបង្ហាញ Heap Sort
- ជ្រើសរើស ទំហំ array និង ទិន្នន័យបញ្ចូល៖ ចៃដន្យ ជិតតម្រៀបរួច បញ្ច្រាស ឬមានតម្លៃដូចគ្នាច្រើន។ អ្នកក៏អាចវាយបញ្ចូលលេខផ្ទាល់ខ្លួនបានដែរ។
- ចុច Play ដើម្បីមើលការតម្រៀប ឬ Step ដើម្បីដើរមួយការប្រៀបធៀប ឬមួយការ swap ម្តង។ Back ថយក្រោយមួយជំហាន។
- តាមដានពណ៌៖ របារពណ៌ទឹកក្រូចកំពុងត្រូវបានប្រៀបធៀប ពណ៌ក្រហមកំពុង swap ឬសរសេរ ហើយពណ៌បៃតងស្ថិតនៅទីតាំងចុងក្រោយត្រឹមត្រូវ។
- អានសារខាងក្រោមប៊ូតុងបញ្ជា និងបន្ទាត់ pseudocode ដែលបាន highlight ដើម្បីដឹងច្បាស់ពីអ្វីដែល algorithm កំពុងធ្វើ។
- ផ្លាស់ប្តូរ ល្បឿន ប្តូរផ្ទាំងកូដទៅ C++, Java, Python ឬ JavaScript និងប្រៀបធៀបចំនួនរាប់ជាមួយទិន្នន័យបញ្ចូលផ្សេងទៀត។
ហេតុអ្វីប្រើ កម្មវិធីបង្ហាញ Heap Sort របស់ ToolOrca
- របារមានចលនាជាមួយប៊ូតុង play, pause, step និង step back
- របាររំកិលល្បឿន និងរបាររំកិលទីតាំងដើម្បីលោតទៅជំហានណាមួយ
- ការរាប់ចំនួនប្រៀបធៀប និងចំនួន swap
- ទិន្នន័យចៃដន្យ ជិតតម្រៀបរួច បញ្ច្រាស និងមានតម្លៃដូចគ្នាច្រើន ឬលេខផ្ទាល់ខ្លួន
- Highlight បន្ទាត់ pseudocode សម្រាប់គ្រប់ជំហាន
- កូដជាភាសា C++, Java, Python និង JavaScript
- ដំណើរការលើទូរស័ព្ទ និងថេប្លេត ព្រមទាំងបញ្ជាតាមក្តារចុចបាន
របៀបដែល heap sort ដំណើរការ
ដំណាក់កាលទី 1 បង្កើត heap៖ សម្រាប់ i ពី n/2 − 1 ចុះទៅ 0 ធ្វើការ sift a[i] ចុះក្រោម៖ ប្រៀបធៀបវាជាមួយ children នៅ 2i + 1 និង 2i + 2 ហើយ swap វាជាមួយ child ដែលធំជាង ប្រសិនបើ child នោះធំជាងវា។ ស្លឹក (leaf) មិនបាច់ធ្វើអ្វីទេ ដូច្នេះ loop ចាប់ផ្តើមពី parent ចុងក្រោយ។ ដំណាក់កាលទី 2 តម្រៀប៖ សម្រាប់ end ពី n − 1 ចុះទៅ 1 ធ្វើការ swap a[0] (តម្លៃអតិបរមា) ជាមួយ a[end] រួច sift a[0] ចុះក្រោមក្នុងចំណោមធាតុ end ដំបូង។
Time និង space complexity នៃ heap sort
ការបង្កើត heap ត្រូវការ O(n)។ ការទាញយកនីមួយៗក្នុងចំណោម n − 1 លើក sift ចុះក្រោមយ៉ាងច្រើន log₂ n កម្រិត ដូច្នេះសរុបគឺ O(n log n) ទាំងករណីល្អបំផុត មធ្យម និងអាក្រក់បំផុត។ Heap sort តម្រៀប in-place ដោយប្រើ memory បន្ថែមត្រឹម O(1) ដែល merge sort ឬ quick sort មិនអាចធ្វើបានទាំងស្រុង។ វាមិនមែនជា stable sort ទេ ហើយវាលោតចុះឡើងក្នុង array ធ្វើឱ្យវាប្រើប្រាស់ CPU cache មិនសូវល្អដូច quick sort។
ពេលណាគួរប្រើ heap sort
Heap sort ជាជម្រើសមានសុវត្ថិភាពនៅពេលអ្នកត្រូវការរយៈពេល O(n log n) ច្បាស់លាស់ជាមួយ memory បន្ថែមថេរ ឧទាហរណ៍ក្នុង embedded systems។ វាក៏ជាជម្រើសជំនួសក្នុង introsort (C++ std::sort) នៅពេល recursion របស់ quick sort ជ្រៅពេក។ ប្រសិនបើអ្នកត្រូវការតែតម្លៃធំបំផុតចំនួន k អ្នកអាចបញ្ឈប់បន្ទាប់ពីទាញយកបាន k លើក។
រាល់ visualizer លើគេហទំព័រនេះដំណើរការក្នុង browser របស់អ្នកជាមួយប៊ូតុងបញ្ជាដូចគ្នា៖ Play, Pause, Step ទៅមុខ, Step ថយក្រោយ និងរបាររំកិលល្បឿន។ អ្នកក៏អាចអូសរបារទីតាំងដើម្បីលោតទៅជំហានណាមួយ ឬចុចលើផ្ទាំងគំនូរហើយប្រើ Space bar និងគ្រាប់ចុចព្រួញ។
សំណួរដែលសួរញឹកញាប់
តើ time complexity របស់ heap sort គឺជាអ្វី?
O(n log n) គ្រប់ករណីទាំងអស់៖ O(n) ដើម្បីបង្កើត heap បូកនឹងការទាញយក n ដងដែលម្តងៗចំណាយ O(log n)។
តើ heap sort ជា stable sort ដែរឬទេ?
មិនមែនទេ ព្រោះការ swap root ជាមួយធាតុចុងក្រោយ និងការ sift down អាចផ្លាស់ប្តូរលំដាប់នៃតម្លៃស្មើគ្នា។
ហេតុអ្វី heap sort ប្រើ max-heap ដើម្បីតម្រៀបតាមលំដាប់ឡើង?
តម្លៃអតិបរមាត្រូវបានដកចេញមុនគេ ហើយយកទៅដាក់នៅចុង array ដូច្នេះផ្នែកដែលតម្រៀបរួចនឹងកើនឡើងពីស្តាំទៅឆ្វេងតាមលំដាប់ឡើង។
រវាង heap sort និង quick sort មួយណាល្អជាង?
Quick sort ជាទូទៅលឿនជាងក្នុងការអនុវត្តជាក់ស្តែង ប៉ុន្តែ heap sort ធានា O(n log n) និងប្រើ memory បន្ថែមត្រឹម O(1)។ Introsort រួមបញ្ចូលវិធីទាំងពីរនេះចូលគ្នា។