Chèn và Xóa trong Heap (Insertion and Deletion in Heaps) trong Cấu trúc dữ liệu

Xem cách chèn và xóa phần tử từ cấu trúc dữ liệu binary heap. Giả sử cây ban đầu như sau:

Thuật toán Chèn (Insertion)

insert(heap, n, item): Begin
    if heap đầy, then exit
    else
        n := n + 1
        for i := n, i > 1, i := i / 2 mỗi vòng, do
            if item <= heap[i/2], then break
            heap[i] = heap[i/2]
        done
    end if
    heap[i] := item
End

Ví dụ

Giả sử chèn 30 vào heap:

Thuật toán Xóa (Deletion)

delete(heap, n): Begin
    if heap rỗng, then exit
    else
        item := heap[1]
        last := heap[n]
        n := n – 1
        for i := 1, j := 2, j <= n, i := j, j := j * 2, do
            if j < n, then
                if heap[j] < heap[j + 1], then j := j + 1
            end if
            if last >= heap[j], then break
            heap[i] := heap[j]
        done
    end if
    heap[i] := last
End

Ví dụ

Giả sử xóa 30 từ heap cuối: