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

Heap Sort เป็นเทคนิคการเรียงลำดับตามโครงสร้างข้อมูลไบนารีฮีป เพื่อดำเนินการเรียงลำดับแบบฮีป คุณต้องทำความคุ้นเคยกับไบนารีทรีและไบนารีฮีป

ต้นไม้ไบนารีที่สมบูรณ์คืออะไร

ต้นไม้ไบนารีที่สมบูรณ์เป็นโครงสร้างข้อมูลต้นไม้ที่ระดับทั้งหมดยกเว้นระดับสุดท้ายจะเต็มไปหมด ต้องกรอกระดับสุดท้ายจากด้านซ้าย

ไบนารี่ฮีปคืออะไร

Binary heap เป็นกรณีพิเศษของไบนารีทรี Binary heaps มีสองประเภท -

• Max Heap - โหนดหลักในแต่ละระดับมากกว่าโหนดย่อย

• Min Heap − โหนดหลักในแต่ละระดับมีขนาดเล็กกว่าโหนดย่อย

การแสดงอาร์เรย์ของต้นไม้ไบนารีที่สมบูรณ์

ไบนารีฮีปสามารถแสดงเป็นอาร์เรย์ได้เนื่องจากมีพื้นที่ว่างอย่างมีประสิทธิภาพ หากโหนดหลักถูกเก็บไว้ที่ดัชนี I ลูกด้านซ้ายสามารถคำนวณได้โดย 2 * i + 1 และลูกที่ถูกต้องโดย 2 *i + 2 สมมติว่าดัชนีเริ่มต้นจาก 0

อัลกอริทึมการเรียงลำดับฮีป

• สร้างฮีปสูงสุดจากไบนารีทรีที่สมบูรณ์

• ลบรูทและแทนที่ด้วยองค์ประกอบสุดท้ายในฮีป ลดขนาดของฮีปลง 1 และสร้างฮีปสูงสุดอีกครั้งจากโหนดที่เหลือ

• ทำซ้ำขั้นตอนที่ 2 จนกว่าเราจะเหลือเพียง 1 โหนด

สร้างฮีปสูงสุดจากทรีไบนารีที่สมบูรณ์

นี่คือรหัสสำหรับสร้างฮีปสูงสุดจากทรีไบนารีที่สมบูรณ์ โดยที่โหนดย่อยทั้งสองจะถูกเปรียบเทียบกับรูท หากองค์ประกอบที่ใหญ่กว่าไม่ใช่รูท ให้สลับองค์ประกอบที่ใหญ่กว่ากับรูท นี่เป็นขั้นตอนแบบเรียกซ้ำ รูทปัจจุบันซึ่งเล็กกว่าโหนดย่อยจะถูกเปรียบเทียบกับทรีย่อยที่ต่ำกว่าอย่างต่อเนื่อง เว้นแต่จะถึงตำแหน่งที่ถูกต้อง

รหัสต่อไปนี้สร้างฮีปสูงสุดจากต้นไม้ไบนารีที่สมบูรณ์ ซึ่งโดยพื้นฐานแล้วคืออาร์เรย์ที่เราต้องการจัดเรียง

def heapify(arr, n, i):
   # Find largest among root and children
   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 root is not largest, swap with largest and continue heapifying
   if largest != i:
      arr[i], arr[largest] = arr[largest], arr[i]
      heapify(arr, n, largest)

การเรียงลำดับฮีป

ณ เวลานี้ เรามีฮีปสูงสุดอยู่กับเรา ตอนนี้เราต้องทำสิ่งต่อไปนี้

• สลับรูทกับองค์ประกอบสุดท้ายในฮีป

• ลดขนาดของฮีปลง 1 (ซึ่งหมายความว่าองค์ประกอบที่ใหญ่ที่สุดมาถึงตำแหน่งสุดท้ายแล้ว เราไม่จำเป็นต้องพิจารณาองค์ประกอบนั้น)

• สร้างฮีปสูงสุดใหม่โดยไม่รวมองค์ประกอบสุดท้าย

• ทำซ้ำขั้นตอนข้างต้นจนกว่าเราจะเหลือเพียง 1 องค์ประกอบ

for i in range(n-1, 0, -1):
   # Swap
   arr[i], arr[0] = arr[0], arr[i]

   # Heapify root element
   heapify(arr, i, 0)

โปรแกรมที่สมบูรณ์สำหรับการเรียงลำดับฮีปใน Python มีดังต่อไปนี้ -

def heapify(arr, n, i):
   # Find largest among root and children
   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 root is not largest, swap with largest and continue heapifying
   if largest != i:
      arr[i], arr[largest] = arr[largest], arr[i]
      heapify(arr, n, largest)

def heapSort(arr):
   n = len(arr)
   # Build max heap
   for i in range(n//2, -1, -1):
      heapify(arr, n, i)
   for i in range(n-1, 0, -1):
      # Swap
      arr[i], arr[0] = arr[0], arr[i]
      # Heapify root element
      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=' ')

ความซับซ้อนของเวลา - O(n logn)