ការតម្រៀបបែបគំនរ
បច្ចេកទេសតម្រៀបផ្អែកលើការប្រៀបធៀបដែលផ្អែកលើរចនាសម្ព័ន្ធទិន្នន័យ Binary Heap។ វាស្រដៀងនឹងការតម្រៀបបែបជ្រើសរើស។
Visualization
Details
Analogy
ពិចារណាពីแผนผังองค์กรតាមລำดับชั้นของបริษัทដែលមីโครงสร้างเป็น 'max heap' ដែលผู้จัดการทุกคนមีរายได้มากกว่าผู้ใต้បັงคับบัญชาโดยตรงของตন។ CEO ที่อยู่ด้านบนสุดคือผู้ที่មีរายได้สูงสุด។ คุณ 'ลบ' CEO ออก เลื่อนตำแหน่งผู้ที่មีរายได้สูงสุดคนถัดไป และจัດระเบียบแผนผังใหม่เพื่อหาผู้ที่មีរายได้สูงสุดคนถัดไป ทำซ้ำจนกว่าทุกคนจะถูกจัดเรียงตามเงินเดือน។
Purpose
ដើម្បីតម្រៀបអារេដោយដំបូងបង្កើត max heap ពីទិន្នន័យ បន្ទាប់មកដកធាតុធំបំផុតចេញពី heap ម្ដងហើយម្ដងទៀត ហើយដាក់វានៅចុងផ្នែកដែលបានតម្រៀប។
Use Cases
มีประโยชน់เมื่อต้องการประสิทธิภาพกรณีเลวร้ายที่สุดที่รับประกัน O(n log n)។ มันไม่เสถียร และโดยทั่วไปแล้วจะช้ากว่า Quick Sort ที่実装อย่างดีในทางปฏิบัติ។
Algorithm Steps
build max heap from array
for i = n-1 to 1:
swap arr[0] with arr[i]
heapify(arr, 0, i)
function heapify(arr, i, size):
largest = i
left = 2*i + 1
right = 2*i + 2
if left < size and arr[left] > arr[largest]:
largest = left
if right < size and arr[right] > arr[largest]:
largest = right
if largest != i:
swap arr[i] with arr[largest]
heapify(arr, largest, size)
Explanation
What's Happening?
អារេដំបូង។ ចាប់ផ្តើមสร้าง max heap។
Code Implementation
def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
return arr
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[l] > arr[largest]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)