ฮีปทวิภาค (อังกฤษ: binary heap) เป็นโครงสร้างข้อมูลฮีปที่อยู่ในรูปแบบของต้นไม้แบบทวิภาค มักถูกใช้เพื่อจัดแถวคอยลำดับความสำคัญ[1]

การจัดเรียฮีปแบบแถวลำดับพลวัต

Min Heapแก้ไข

  min heap จัดเรียงในรูปแบบของtree เป็นการจัดลำดับจากน้อยไปมากโดยใส่ฝั่งซ้ายไปขวา

Binary Min Heap

Max Heapแก้ไข

  max heap จัดเรียงในรูปแบบของtree เป็นการจัดลำดับจากมากไปน้อยโดยใส่ฝั่งซ้ายไปขวา

Binary Max Heap

Coding Pythonแก้ไข

 1 def heapify(array, n, i):
 2     largest = i
 3     l = 2 * i + 1
 4     r = 2 * i + 2
 5 
 6     if l < n and array[i] < array[l]:
 7         largest = l
 8 
 9     if r < n and array[largest] < array[r]:
10         largest = r
11 
12     if largest != i:
13         array[i],array[largest] = array[largest],array[i]
14         heapify(array, n, largest)
15         
16 def heapSort(array):
17     n = len(array)
18     for i in range(n, -1, -1):
19         heapify(array, n, i)
20     for i in range(n-1, 0, -1):
21         array[i],array[0] = array[0],array[i]
22         heapify(array, i, 0)
23     return array

อ้างอิงแก้ไข

  1. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.