โปรแกรม Python สำหรับ Heap Sort

ในบทความนี้ เราจะเรียนรู้วิธีการแก้ปัญหาต่อไปนี้:

ข้อความปัญหา — กำหนดอาร์เรย์ ให้จัดเรียงโดยใช้แนวคิดของ Heap Sort

ที่นี่เราจะวางองค์ประกอบสูงสุดไว้ที่ท้าย สิ่งนี้จะทำซ้ำจนกว่าอาร์เรย์จะถูกจัดเรียง

มาเปลี่ยนดูโค้ดตัวอย่างด้านล่างนี้:

ตัวอย่างโค้ด

# ฟังก์ชัน heapify
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
        heapify(arr, n, largest)

# ฟังก์ชันจัดเรียง
def heapSort(arr):
    n = len(arr)
    # สร้าง max heap
    for i in range(n, -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 = [2, 5, 3, 8, 6, 5, 4, 7]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
    print(arr[i], end=" ")

ผลลัพธ์

Sorted array is 2 3 4 5 5 6 7 8

ตัวแปรทั้งหมดถูกประกาศในขอบเขตท้องถิ่น (local scope) และการอ้างอิงของมันแสดงในรูปภาพด้านบน

สรุป

ในบทความนี้ เราได้เรียนรู้วิธีการเขียนโปรแกรม Python สำหรับ Heap Sort