ฮีปทวิภาค

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

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

Min Heap

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

Binary Min Heap

Max Heap

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

Binary Max Heap

Coding Python

def heapify(array, n, i):  largest = i  l = 2 * i + 1  r = 2 * i + 2   if l < n and array[i] < array[l]:  largest = l   if r < n and array[largest] < array[r]:  largest = r   if largest != i:  array[i],array[largest] = array[largest],array[i]  heapify(array, n, largest)  def heapSort(array):  n = len(array)  for i in range(n, -1, -1):  heapify(array, n, i)  for i in range(n-1, 0, -1):  array[i],array[0] = array[0],array[i]  heapify(array, i, 0)  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.