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

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

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.