home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

Heap Sort ใน Python คืออะไร

Heap Sort คืออะไร

Heap Sort เป็นอัลกอริทึมการจัดเรียงที่อิงโครงสร้างข้อมูล Binary Heap ก่อนเรียนรู้ Heap Sort ควรเข้าใจ Binary Tree และ Binary Heap ก่อน

Complete Binary Tree คืออะไร

Complete Binary Tree คือต้นไม้ที่ทุกระดับเต็มไปด้วยโหนด ยกเว้นระดับสุดท้ายที่ต้องเต็มจากซ้ายไปขวา

Binary Heap คืออะไร

Binary Heap เป็นกรณีพิเศษของ Binary Tree แบ่งเป็น 2 ประเภท:

  • Max Heap: โหนดพ่อมีค่ามากกว่าลูกทุกคู่
  • Min Heap: โหนดพ่อมีค่าน้อยกว่าลูกทุกคู่

Array Representation ของ Complete Binary Tree

Binary Heap แทนเป็น Array ได้เพราะประหยัดพื้นที่ หากพ่ออยู่ index i ลูกซ้าย = 2*i+1 ลูกขวา = 2*i+2 (index เริ่มที่ 0)

Heap Sort Algorithm

  1. สร้าง Max Heap จาก Complete Binary Tree
  2. สลับ Root กับโหนดสุดท้าย ลดขนาด heap 1 สร้าง Max Heap ใหม่จากโหนดที่เหลือ
  3. ทำซ้ำข้อ 2 จนเหลือ 1 โหนด

ฟังก์ชัน Heapify (สร้าง Max Heap)

def heapify(arr, n, i):
    # หาค่าสูงสุดระหว่าง root และลูก
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    # ถ้า root ไม่ใช่ค่าสูงสุด สลับและ heapify ต่อ
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

Heap Sort หลัก

def heapSort(arr):
    n = len(arr)
    # สร้าง max heap
    for i in range(n//2, -1, -1):
        heapify(arr, n, i)
    # สลับและ heapify ซ้ำ
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # สลับ
        heapify(arr, i, 0)  # heapify root

โปรแกรมสมบูรณ์

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)
    for i in range(n//2, -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)

arr = [1, 12, 9, 5, 6, 10]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
    print(arr[i], end=' ')

ผลลัพธ์

Sorted array is
1 5 6 9 10 12

Time Complexity

O(n log n) ในทุกกรณี (best, average, worst)