Đống

Một đống (heap) là một cây nhị phân hoàn chỉnh thỏa mãn các điều kiện cụ thể và chủ yếu được chia thành hai loại, như được hiển thị trong hình bên dưới.

• đống cực tiểu (min heap): Giá trị của bất kỳ nút nào \(\leq\) giá trị của các nút con của nó.
• đống cực đại (max heap): Giá trị của bất kỳ nút nào \(\geq\) giá trị của các nút con của nó.

Là một trường hợp đặc biệt của cây nhị phân hoàn chỉnh, đống có các đặc điểm sau:

• Các nút ở tầng dưới cùng được điền từ trái qua phải, và các nút ở các tầng khác được điền đầy đủ.
• Chúng ta gọi nút gốc của cây nhị phân là "đỉnh đống" (heap top) và nút ngoài cùng bên phải ở tầng dưới cùng là "đáy đống" (heap bottom).
• Đối với đống cực đại (đống cực tiểu), giá trị của phần tử đỉnh đống (nút gốc) là lớn nhất (nhỏ nhất).

Các thao tác cơ bản với Đống

Cần lưu ý rằng nhiều ngôn ngữ lập trình cung cấp hàng đợi ưu tiên (priority queue), một cấu trúc dữ liệu trừu tượng được định nghĩa là một hàng đợi mà các phần tử được sắp xếp theo mức độ ưu tiên.

Trên thực tế, đống thường được sử dụng để triển khai hàng đợi ưu tiên, trong đó đống cực đại tương ứng với hàng đợi ưu tiên có các phần tử được lấy ra theo thứ tự giảm dần. Đứng từ góc độ sử dụng, chúng ta có thể coi "hàng đợi ưu tiên" và "đống" là các cấu trúc dữ liệu tương đương nhau. Vì vậy, cuốn sách này không đưa ra sự phân biệt đặc biệt giữa cả hai và thống nhất gọi chung là "đống" (heap).

Các thao tác phổ biến trên đống được trình bày trong bảng dưới đây, và tên phương thức cần được xác định dựa trên ngôn ngữ lập trình cụ thể.

Bảng   Hiệu suất của các thao tác trên Đống

Tên phương thức	Mô tả	Độ phức tạp thời gian
push()	Thêm một phần tử vào đống	\(O(\log n)\)
pop()	Loại bỏ phần tử đỉnh đống	\(O(\log n)\)
peek()	Truy cập phần tử đỉnh đống (giá trị lớn nhất/nhỏ nhất tương ứng với đống cực đại/đống cực tiểu)	\(O(1)\)
size()	Lấy số lượng phần tử trong đống	\(O(1)\)
isEmpty()	Kiểm tra xem đống có trống không	\(O(1)\)

Trong ứng dụng thực tế, chúng ta có thể trực tiếp sử dụng lớp đống (hoặc lớp hàng đợi ưu tiên) do ngôn ngữ lập trình cung cấp.

Tương tự như "thứ tự tăng dần" và "thứ tự giảm dần" trong các thuật toán sắp xếp, chúng ta có thể triển khai chuyển đổi giữa "đống cực tiểu" và "đống cực đại" bằng cách thiết lập một biến cờ flag hoặc sửa đổi bộ so sánh Comparator. Mã nguồn cụ thể như sau:

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

heap.py

# Khởi tạo đống cực tiểu
min_heap, flag = [], 1
# Khởi tạo đống cực đại
max_heap, flag = [], -1

# Module heapq của Python mặc định triển khai đống cực tiểu
# Cân nhắc việc đổi dấu (phủ định) phần tử trước khi thêm vào đống, việc này sẽ đảo ngược quan hệ kích thước và do đó triển khai được đống cực đại
# Trong ví dụ này, flag = 1 tương ứng với đống cực tiểu, flag = -1 tương ứng với đống cực đại

# Thêm phần tử vào đống
heapq.heappush(max_heap, flag * 1)
heapq.heappush(max_heap, flag * 3)
heapq.heappush(max_heap, flag * 2)
heapq.heappush(max_heap, flag * 5)
heapq.heappush(max_heap, flag * 4)

# Lấy phần tử đỉnh đống
peek: int = flag * max_heap[0] # 5

# Loại bỏ phần tử đỉnh đống
# Các phần tử được lấy ra sẽ tạo thành một chuỗi giảm dần
val = flag * heapq.heappop(max_heap) # 5
val = flag * heapq.heappop(max_heap) # 4
val = flag * heapq.heappop(max_heap) # 3
val = flag * heapq.heappop(max_heap) # 2
val = flag * heapq.heappop(max_heap) # 1

# Lấy kích thước đống
size: int = len(max_heap)

# Kiểm tra xem đống có trống không
is_empty: bool = not max_heap

# Dựng một đống từ danh sách đầu vào
min_heap: list[int] = [1, 3, 2, 5, 4]
heapq.heapify(min_heap)

heap.cpp

/* Khởi tạo đống */
// Khởi tạo đống cực tiểu
priority_queue<int, vector<int>, greater<int>> minHeap;
// Khởi tạo đống cực đại
priority_queue<int, vector<int>, less<int>> maxHeap;

/* Thêm phần tử vào đống */
maxHeap.push(1);
maxHeap.push(3);
maxHeap.push(2);
maxHeap.push(5);
maxHeap.push(4);

/* Lấy phần tử đỉnh đống */
int peek = maxHeap.top(); // 5

/* Loại bỏ phần tử đỉnh đống */
// Các phần tử được lấy ra sẽ tạo thành một chuỗi giảm dần
maxHeap.pop(); // 5
maxHeap.pop(); // 4
maxHeap.pop(); // 3
maxHeap.pop(); // 2
maxHeap.pop(); // 1

/* Lấy kích thước đống */
int size = maxHeap.size();

/* Kiểm tra xem đống có trống không */
bool isEmpty = maxHeap.empty();

/* Dựng một đống từ danh sách đầu vào */
vector<int> input{1, 3, 2, 5, 4};
priority_queue<int, vector<int>, greater<int>> minHeap(input.begin(), input.end());

heap.java

/* Khởi tạo đống */
// Khởi tạo đống cực tiểu
Queue<Integer> minHeap = new PriorityQueue<>();
// Khởi tạo đống cực đại (sử dụng biểu thức lambda để sửa đổi Comparator)
Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

/* Thêm phần tử vào đống */
maxHeap.offer(1);
maxHeap.offer(3);
maxHeap.offer(2);
maxHeap.offer(5);
maxHeap.offer(4);

/* Lấy phần tử đỉnh đống */
int peek = maxHeap.peek(); // 5

/* Loại bỏ phần tử đỉnh đống */
// Các phần tử được lấy ra sẽ tạo thành một chuỗi giảm dần
peek = maxHeap.poll(); // 5
peek = maxHeap.poll(); // 4
peek = maxHeap.poll(); // 3
peek = maxHeap.poll(); // 2
peek = maxHeap.poll(); // 1

/* Lấy kích thước đống */
int size = maxHeap.size();

/* Kiểm tra xem đống có trống không */
boolean isEmpty = maxHeap.isEmpty();

/* Dựng một đống từ danh sách đầu vào */
minHeap = new PriorityQueue<>(Arrays.asList(1, 3, 2, 5, 4));

heap.cs

/* Khởi tạo đống */
// Khởi tạo đống cực tiểu
PriorityQueue<int, int> minHeap = new();
// Khởi tạo đống cực đại (sử dụng biểu thức lambda để sửa đổi Comparer)
PriorityQueue<int, int> maxHeap = new(Comparer<int>.Create((x, y) => y.CompareTo(x)));

/* Thêm phần tử vào đống */
maxHeap.Enqueue(1, 1);
maxHeap.Enqueue(3, 3);
maxHeap.Enqueue(2, 2);
maxHeap.Enqueue(5, 5);
maxHeap.Enqueue(4, 4);

/* Lấy phần tử đỉnh đống */
int peek = maxHeap.Peek();//5

/* Loại bỏ phần tử đỉnh đống */
// Các phần tử được lấy ra sẽ tạo thành một chuỗi giảm dần
peek = maxHeap.Dequeue();  // 5
peek = maxHeap.Dequeue();  // 4
peek = maxHeap.Dequeue();  // 3
peek = maxHeap.Dequeue();  // 2
peek = maxHeap.Dequeue();  // 1

/* Lấy kích thước đống */
int size = maxHeap.Count;

/* Kiểm tra xem đống có trống không */
bool isEmpty = maxHeap.Count == 0;

/* Dựng một đống từ danh sách đầu vào */
minHeap = new PriorityQueue<int, int>([(1, 1), (3, 3), (2, 2), (5, 5), (4, 4)]);

heap.go

// Trong Go, chúng ta có thể dựng một đống cực đại chứa các số nguyên bằng cách triển khai heap.Interface
// Việc triển khai heap.Interface cũng yêu cầu triển khai sort.Interface
type intHeap []any

// Push triển khai phương thức heap.Interface để thêm một phần tử vào đống
func (h *intHeap) Push(x any) {
    // Push và Pop sử dụng con trỏ nhận (pointer receiver) làm tham số
    // vì chúng không chỉ điều chỉnh nội dung lát cắt (slice) mà còn thay đổi độ dài của lát cắt
    *h = append(*h, x.(int))
}

// Pop triển khai phương thức heap.Interface để loại bỏ phần tử đỉnh đống
func (h *intHeap) Pop() any {
    // Phần tử cần loại bỏ được lưu ở cuối
    last := (*h)[len(*h)-1]
    *h = (*h)[:len(*h)-1]
    return last
}

// Len là phương thức của sort.Interface
func (h *intHeap) Len() int {
    return len(*h)
}

// Less là phương thức của sort.Interface
func (h *intHeap) Less(i, j int) bool {
    // Để triển khai đống cực tiểu, hãy thay dấu lớn hơn thành dấu nhỏ hơn
    return (*h)[i].(int) > (*h)[j].(int)
}

// Swap là phương thức của sort.Interface
func (h *intHeap) Swap(i, j int) {
    (*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}

// Top lấy phần tử đỉnh đống
func (h *intHeap) Top() any {
    return (*h)[0]
}

/* Mã chạy thử */
func TestHeap(t *testing.T) {
    /* Khởi tạo đống */
    // Khởi tạo đống cực đại
    maxHeap := &intHeap{}
    heap.Init(maxHeap)
    /* Thêm phần tử vào đống */
    // Gọi các phương thức heap.Interface để thêm phần tử
    heap.Push(maxHeap, 1)
    heap.Push(maxHeap, 3)
    heap.Push(maxHeap, 2)
    heap.Push(maxHeap, 4)
    heap.Push(maxHeap, 5)

    /* Lấy phần tử đỉnh đống */
    top := maxHeap.Top()
    fmt.Printf("Phần tử đỉnh đống là %d\n", top)

    /* Loại bỏ phần tử đỉnh đống */
    // Gọi các phương thức heap.Interface để loại bỏ phần tử
    heap.Pop(maxHeap) // 5
    heap.Pop(maxHeap) // 4
    heap.Pop(maxHeap) // 3
    heap.Pop(maxHeap) // 2
    heap.Pop(maxHeap) // 1

    /* Lấy kích thước đống */
    size := len(*maxHeap)
    fmt.Printf("Số lượng phần tử trong đống là %d\n", size)

    /* Kiểm tra xem đống có trống không */
    isEmpty := len(*maxHeap) == 0
    fmt.Printf("Đống có trống không? %t\n", isEmpty)
}

heap.swift

/* Khởi tạo đống */
// Kiểu Heap của Swift hỗ trợ cả đống cực đại và đống cực tiểu, và yêu cầu nhập (import) swift-collections
var heap = Heap<Int>()

/* Thêm phần tử vào đống */
heap.insert(1)
heap.insert(3)
heap.insert(2)
heap.insert(5)
heap.insert(4)

/* Lấy phần tử đỉnh đống */
var peek = heap.max()!

/* Loại bỏ phần tử đỉnh đống */
peek = heap.removeMax() // 5
peek = heap.removeMax() // 4
peek = heap.removeMax() // 3
peek = heap.removeMax() // 2
peek = heap.removeMax() // 1

/* Lấy kích thước đống */
let size = heap.count

/* Kiểm tra xem đống có trống không */
let isEmpty = heap.isEmpty

/* Dựng một đống từ danh sách đầu vào */
let heap2 = Heap([1, 3, 2, 5, 4])

heap.js

// JavaScript không cung cấp lớp Heap dựng sẵn

heap.ts

// TypeScript không cung cấp lớp Heap dựng sẵn

heap.dart

// Dart không cung cấp lớp Heap dựng sẵn

heap.rs

use std::collections::BinaryHeap;
use std::cmp::Reverse;

/* Khởi tạo đống */
// Khởi tạo đống cực tiểu
let mut min_heap = BinaryHeap::<Reverse<i32>>::new();
// Khởi tạo đống cực đại
let mut max_heap = BinaryHeap::new();

/* Thêm phần tử vào đống */
max_heap.push(1);
max_heap.push(3);
max_heap.push(2);
max_heap.push(5);
max_heap.push(4);

/* Lấy phần tử đỉnh đống */
let peek = max_heap.peek().unwrap();  // 5

/* Loại bỏ phần tử đỉnh đống */
// Các phần tử được lấy ra sẽ tạo thành một chuỗi giảm dần
let peek = max_heap.pop().unwrap();   // 5
let peek = max_heap.pop().unwrap();   // 4
let peek = max_heap.pop().unwrap();   // 3
let peek = max_heap.pop().unwrap();   // 2
let peek = max_heap.pop().unwrap();   // 1

/* Lấy kích thước đống */
let size = max_heap.len();

/* Kiểm tra xem đống có trống không */
let is_empty = max_heap.is_empty();

/* Dựng một đống từ danh sách đầu vào */
let min_heap = BinaryHeap::from(vec![Reverse(1), Reverse(3), Reverse(2), Reverse(5), Reverse(4)]);

heap.c

// C không cung cấp lớp Heap dựng sẵn

heap.kt

/* Khởi tạo đống */
// Khởi tạo đống cực tiểu
var minHeap = PriorityQueue<Int>()
// Khởi tạo đống cực đại (sử dụng biểu thức lambda để sửa đổi Comparator)
val maxHeap = PriorityQueue { a: Int, b: Int -> b - a }

/* Thêm phần tử vào đống */
maxHeap.offer(1)
maxHeap.offer(3)
maxHeap.offer(2)
maxHeap.offer(5)
maxHeap.offer(4)

/* Lấy phần tử đỉnh đống */
var peek = maxHeap.peek() // 5

/* Loại bỏ phần tử đỉnh đống */
// Các phần tử được lấy ra sẽ tạo thành một chuỗi giảm dần
peek = maxHeap.poll() // 5
peek = maxHeap.poll() // 4
peek = maxHeap.poll() // 3
peek = maxHeap.poll() // 2
peek = maxHeap.poll() // 1

/* Lấy kích thước đống */
val size = maxHeap.size

/* Kiểm tra xem đống có trống không */
val isEmpty = maxHeap.isEmpty()

/* Dựng một đống từ danh sách đầu vào */
minHeap = PriorityQueue(mutableListOf(1, 3, 2, 5, 4))

heap.rb

# Ruby không cung cấp lớp Heap dựng sẵn

Trực quan hóa mã nguồn

https://pythontutor.com/render.html#code=import%20heapq%0A%0A%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E5%B0%8F%E9%A1%B6%E5%A0%86%0A%20%20%20%20min_heap,%20flag%20%3D%20%5B%5D,%201%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E5%A4%A7%E9%A1%B6%E5%A0%86%0A%20%20%20%20max_heap,%20flag%20%3D%20%5B%5D,%20-1%0A%20%20%20%20%0A%20%20%20%20%23%20Python%20%E7%9A%84%20heapq%20%E6%A8%A1%E5%9D%97%E9%BB%98%E8%AE%A4%E5%AE%9E%E7%8E%B0%E5%B0%8F%E9%A1%B6%E5%A0%86%0A%20%20%20%20%23%20%E8%80%83%E8%99%91%E5%B0%86%E2%80%9C%E5%85%83%E7%B4%A0%E5%8F%96%E8%B4%9F%E2%80%9D%E5%90%8E%E5%86%8D%E5%85%A5%E5%A0%86%EF%BC%8C%E8%BF%99%E6%A0%B7%E5%B0%B1%E5%8F%AF%E4%BB%A5%E5%B0%86%E5%A4%A7%E5%B0%8F%E5%85%B3%E7%B3%BB%E9%A2%A0%E5%80%92%EF%BC%8C%E4%BB%8E%E8%80%8C%E5%AE%9E%E7%8E%B0%E5%A4%A7%E9%A1%B6%E5%A0%86%0A%20%20%20%20%23%20%E5%9C%A8%E6%9C%AC%E7%A4%BA%E4%BE%8B%E4%B8%AD%EF%BC%8Cflag%20%3D%201%20%E6%97%B6%E5%AF%B9%E5%BA%94%E5%B0%8F%E9%A1%B6%E5%A0%86%EF%BC%8Cflag%20%3D%20-1%20%E6%97%B6%E5%AF%B9%E5%BA%94%E5%A4%A7%E9%A1%B6%E5%A0%86%0A%20%20%20%20%0A%20%20%20%20%23%20%E5%85%83%E7%B4%A0%E5%85%A5%E5%A0%86%0A%20%20%20%20heapq.heappush%28max_heap,%20flag%20*%201%29%0A%20%20%20%20heapq.heappush%28max_heap,%20flag%20*%203%29%0A%20%20%20%20heapq.heappush%28max_heap,%20flag%20*%202%29%0A%20%20%20%20heapq.heappush%28max_heap,%20flag%20*%205%29%0A%20%20%20%20heapq.heappush%28max_heap,%20flag%20*%204%29%0A%20%20%20%20%0A%20%20%20%20%23%20%E8%8E%B7%E5%8F%96%E5%A0%86%E9%A1%B6%E5%85%83%E7%B4%A0%0A%20%20%20%20peek%20%3D%20flag%20*%20max_heap%5B0%5D%20%23%205%0A%20%20%20%20%0A%20%20%20%20%23%20%E5%A0%86%E9%A1%B6%E5%85%83%E7%B4%A0%E5%87%BA%E5%A0%86%0A%20%20%20%20%23%20%E5%87%BA%E5%A0%86%E5%85%83%E7%B4%A0%E4%BC%9A%E5%BD%A2%E6%88%90%E4%B8%80%E4%B8%AA%E4%BB%8E%E5%A4%A7%E5%88%B0%E5%B0%8F%E7%9A%84%E5%BA%8F%E5%88%97%0A%20%20%20%20val%20%3D%20flag%20*%20heapq.heappop%28max_heap%29%20%23%205%0A%20%20%20%20val%20%3D%20flag%20*%20heapq.heappop%28max_heap%29%20%23%204%0A%20%20%20%20val%20%3D%20flag%20*%20heapq.heappop%28max_heap%29%20%23%203%0A%20%20%20%20val%20%3D%20flag%20*%20heapq.heappop%28max_heap%29%20%23%202%0A%20%20%20%20val%20%3D%20flag%20*%20heapq.heappop%28max_heap%29%20%23%201%0A%20%20%20%20%0A%20%20%20%20%23%20%E8%8E%B7%E5%8F%96%E5%A0%86%E5%A4%A7%E5%B0%8F%0A%20%20%20%20size%20%3D%20len%28max_heap%29%0A%20%20%20%20%0A%20%20%20%20%23%20%E5%88%A4%E6%96%AD%E5%A0%86%E6%98%AF%E5%90%A6%E4%B8%BA%E7%A9%BA%0A%20%20%20%20is_empty%20%3D%20not%20max_heap%0A%20%20%20%20%0A%20%20%20%20%23%20%E8%BE%93%E5%85%A5%E5%88%97%E8%A1%A8%E5%B9%B6%E5%BB%BA%E5%A0%86%0A%20%20%20%20min_heap%20%3D%20%5B1,%203,%202,%205,%204%5D%0A%20%20%20%20heapq.heapify%28min_heap%29&cumulative=false&curInstr=3&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false

Triển khai cấu trúc Heap

Phần triển khai dưới đây là dành cho đống cực đại. Để chuyển đổi sang đống cực tiểu, chỉ cần đảo ngược tất cả logic so sánh liên quan đến thứ tự (ví dụ: thay \(\geq\) bằng \(\leq\)). Khuyến khích bạn đọc tự mình thử triển khai phần này.

Lưu trữ và biểu diễn Heap

Như đã đề cập trong chương "Cây nhị phân", cây nhị phân hoàn chỉnh rất phù hợp để biểu diễn bằng mảng. Vì đống là một loại cây nhị phân hoàn chỉnh, chúng ta sẽ sử dụng mảng để lưu trữ đống.

Khi biểu diễn một cây nhị phân bằng mảng, các phần tử đại diện cho giá trị của nút và các chỉ số đại diện cho vị trí của nút trong cây nhị phân. Mối quan hệ cha-con được biểu diễn thông qua các công thức ánh xạ chỉ số.

Như trong hình bên dưới, cho một chỉ số \(i\), chỉ số của nút con bên trái là \(2i + 1\), chỉ số của nút con bên phải là \(2i + 2\), và chỉ số của nút cha là \((i - 1) / 2\) (phép chia lấy phần nguyên). Khi một chỉ số vượt quá phạm vi, nó biểu thị một nút rỗng (null node) hoặc nút đó không tồn tại.

Chúng ta có thể đóng gói công thức ánh xạ chỉ số thành các hàm để thuận tiện sử dụng về sau:

[file]{my_heap}-[class]{max_heap}-[func]{parent}

Truy cập phần tử đỉnh đống

Phần tử đỉnh đống là nút gốc của cây nhị phân, đây cũng là phần tử đầu tiên của danh sách:

[file]{my_heap}-[class]{max_heap}-[func]{peek}

Thêm một phần tử vào đống

Cho một phần tử val, trước tiên chúng ta thêm nó vào đáy đống. Sau khi thêm, vì val có thể lớn hơn các phần tử khác trong đống, thuộc tính của đống có thể bị vi phạm. Do đó, chúng ta cần khôi phục lại thuộc tính của đống dọc theo đường đi từ nút vừa chèn đến nút gốc. Thao tác này được gọi là vun đống (heapify).

Bắt đầu từ nút vừa chèn, thực hiện vun đống từ dưới lên trên. Như được hiển thị trong hình bên dưới, chúng ta so sánh nút vừa chèn với nút cha của nó, và nếu nút vừa chèn lớn hơn, chúng ta đổi chỗ chúng. Chúng ta tiếp tục quá trình này từ dưới lên trên cho đến khi vượt qua nút gốc hoặc gặp một nút không cần phải đổi chỗ nữa.

<1><2><3><4><5><6><7><8><9>

Với tổng số \(n\) nút, chiều cao của cây là \(O(\log n)\). Do đó, số lần lặp vòng lặp trong thao tác vun đống tối đa là \(O(\log n)\), làm cho độ phức tạp thời gian của thao tác thêm phần tử là \(O(\log n)\). Mã nguồn cụ thể như sau:

[file]{my_heap}-[class]{max_heap}-[func]{sift_up}

Loại bỏ phần tử đỉnh đống

Phần tử đỉnh đống là nút gốc của cây nhị phân, đây cũng là phần tử đầu tiên của danh sách. Nếu chúng ta trực tiếp loại bỏ phần tử đầu tiên khỏi danh sách, tất cả các chỉ số nút trong cây nhị phân sẽ thay đổi, khiến việc sửa đổi đống sau đó bằng thao tác vun đống trở nên khó khăn. Để hạn chế tối đa các thay đổi đối với chỉ số phần tử, chúng ta thực hiện theo các bước sau:

1. Đổi chỗ phần tử đỉnh đống với phần tử đáy đống (đổi chỗ nút gốc với nút lá ngoài cùng bên phải).
2. Sau khi đổi chỗ, loại bỏ đáy đống khỏi danh sách (lưu ý rằng vì chúng ta đã đổi chỗ nên thực chất chúng ta đang loại bỏ phần tử đỉnh đống ban đầu).
3. Bắt đầu từ nút gốc, thực hiện vun đống từ trên xuống dưới.

Như hiển thị trong hình bên dưới, hướng "vun đống từ trên xuống dưới" ngược lại với "vun đống từ dưới lên trên". Chúng ta so sánh giá trị của nút gốc với hai nút con của nó và đổi chỗ nó với nút con lớn nhất. Sau đó lặp lại thao tác này cho đến khi vượt qua một nút lá hoặc gặp nút không cần phải đổi chỗ nữa.

<1><2><3><4><5><6><7><8><9><10>

Tương tự như thao tác thêm phần tử, độ phức tạp thời gian của thao tác loại bỏ phần tử đỉnh đống cũng là \(O(\log n)\). Mã nguồn cụ thể như sau:

[file]{my_heap}-[class]{max_heap}-[func]{sift_down}

Các ứng dụng phổ biến của Đống

• Hàng đợi ưu tiên: Đống thường là cấu trúc dữ liệu được ưu tiên để triển khai hàng đợi ưu tiên. Độ phức tạp thời gian của cả thao tác thêm vào hàng đợi (enqueue) và lấy ra khỏi hàng đợi (dequeue) đều là \(O(\log n)\), và việc xây dựng đống có độ phức tạp thời gian là \(O(n)\), khiến các thao tác này rất hiệu quả.
• Sắp xếp vun đống (Heap sort): Cho một tập hợp dữ liệu, chúng ta có thể dựng một đống từ chúng và sau đó liên tục thực hiện thao tác loại bỏ phần tử để thu được dữ liệu đã sắp xếp. Tuy nhiên, chúng ta thường sử dụng một cách tiếp cận trang nhã hơn để triển khai sắp xếp vun đống, chi tiết được trình bày trong chương "Sắp xếp vun đống".
• Tìm \(k\) phần tử lớn nhất: Đây là một bài toán thuật toán kinh điển và cũng là một ứng dụng điển hình, chẳng hạn như chọn ra 10 tin tức thịnh hành hàng đầu trên Weibo Hot Search hoặc top 10 sản phẩm bán chạy nhất.