ฮีปทวิภาค

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

Min Heap

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

Max Heap

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

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

อ้างอิง

↑ 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.

[clrs-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.

[1]