👋 Chào mừng đến với Nocoem — kiến thức Backend, System Design và lập trình. Khám phá ngay

Cấu Trúc Dữ liệu: Heaps, Stacks, Queues

Data structures: Heaps Stacks and Queues
Cấu Trúc Dữ liệu: Heaps, Stacks, Queues
TL;DR: Ba cấu trúc dữ liệu kinh điển hay gặp khi phỏng vấn: Stack (LIFO, push/pop O(1)), Queue (FIFO, enqueue/dequeue O(1)) và Heap (hàng đợi ưu tiên, chèn và lấy phần tử nhỏ nhất hoặc lớn nhất O(log n)). Bài này đi qua khái niệm, độ phức tạp, ví dụ Python và một cheat sheet để ôn nhanh trước phỏng vấn.

Những Điều Thiết Yếu Trong Phỏng Vấn

  • Heap: Cấu trúc dữ liệu dạng cây trong đó giá trị của nút cha được sắp xếp theo một cách nhất định so với giá trị của nút con. Heap có thể là min heap (giá trị nút cha nhỏ hơn hoặc bằng giá trị các nút con) hoặc max heap (giá trị nút cha lớn hơn hoặc bằng giá trị các nút con).

  • Stack: Thao tác theo nguyên tắc LIFO (last in first out - vào sau, ra trước), nghĩa là phần tử cuối cùng được thêm vào sẽ là phần tử đầu tiên bị loại bỏ. Stack có thể được triển khai bằng mảng hoặc danh sách liên kết. Nếu stack hết bộ nhớ, được gọi là tràn stack.

  • Queue: Thao tác theo nguyên tắc FIFO (first in first out - vào trước, ra trước), nghĩa là phần tử đầu tiên được thêm vào sẽ là phần tử đầu tiên bị loại bỏ. Queue có thể được triển khai bằng mảng vòng (circular array), danh sách liên kết, hoặc deque.

Cùng với việc nắm vững cách triển khai heap, stack và queue, điều quan trọng là phải rõ ràng về sự khác biệt giữa các cấu trúc dữ liệu này. Trong các cuộc phỏng vấn, việc được hỏi "Giải thích sự khác biệt giữa heap và stack" là rất phổ biến.

Heap là gì?

Mục đích của min-heap là lưu trữ các đối tượng có thứ tự riêng. Nó có phương thức nhanh (O(log n)) để loại bỏ đối tượng nhỏ nhất khỏi heap. Min-heap hữu ích cho các phép tính có nhiều phép tính tìm giá trị nhỏ nhất để thực hiện.

Có một cấu trúc tương tự gọi là max-heap, có thể trích xuất giá trị lớn nhất từ heap.

Một heap chỉ có thể là max-heap hoặc min-heap - không thể là cả hai. Với một triển khai min-heap, max-heap có thể được triển khai bằng cách đảo ngược phép so sánh giữa các phần tử.

Heap đôi khi được gọi là hàng đợi ưu tiên. Về kỹ thuật, heap chỉ là một cách triển khai của hàng đợi ưu tiên.

Đừng nhầm: "Heap" ở đây là cấu trúc dữ liệu (một dạng cây nhị phân dùng làm hàng đợi ưu tiên). Nó khác hoàn toàn với heap memory (vùng nhớ cấp phát động của chương trình, đối lập với stack memory). Trong phỏng vấn, nếu chưa rõ người hỏi đang nói tới nghĩa nào thì cứ hỏi lại ngữ cảnh.

Heap thường được lưu bằng một mảng nhưng hình dung dưới dạng cây nhị phân gần đầy (complete binary tree) sẽ dễ hiểu hơn. Dưới đây là một min-heap:

1 3 5 7 9
Min-heap: mỗi nút cha nhỏ hơn hoặc bằng các nút con (1 <= 3, 1 <= 5, 3 <= 7, 3 <= 9).

Biểu diễn heap bằng mảng

Dù hình dung là cây, heap thường được lưu gọn trong một mảng (không cần con trỏ). Nếu một nút nằm ở chỉ số i (đánh số từ 0) thì:

  • Con trái: left = 2*i + 1
  • Con phải: right = 2*i + 2
  • Nút cha: parent = (i - 1) // 2

Min-heap ở trên được lưu thành [1, 3, 5, 7, 9]: gốc 1 ở chỉ số 0, hai con 3 và 5 ở chỉ số 1 và 2, rồi 7, 9 ở chỉ số 3 và 4. Đây cũng chính là cách heapq của Python biểu diễn heap: chỉ là một list bình thường.

        1(0)
       /    \
     3(1)    5(2)
    /   \
  7(3)  9(4)

Hai thao tác lõi giữ cho heap luôn đúng tính chất:

  • Sift up (khi chèn): thêm phần tử vào cuối mảng rồi liên tục đổi chỗ với nút cha chừng nào nó còn nhỏ hơn cha (min-heap), cho tới khi đúng vị trí. Đi lên theo chiều cao cây nên tốn tối đa O(log n).
  • Sift down (khi lấy min): đưa phần tử cuối lên gốc rồi liên tục đổi chỗ với con nhỏ hơn cho tới khi đúng vị trí. Cũng O(log n).

Heap không phải cây tìm kiếm nhị phân (BST)

Một nhầm lẫn phổ biến: heap và BST cùng là cây nhị phân nhưng phục vụ mục đích khác hẳn nhau.

Tiêu chí Heap Cây tìm kiếm nhị phân (BST)
Thứ tự Chỉ đảm bảo quan hệ cha-con (cha <= con với min-heap) Toàn cây có thứ tự (trái < nút < phải)
Lấy min/max Xem O(1), lấy ra O(log n) O(log n) trung bình
Tìm một giá trị bất kỳ O(n) O(log n) trung bình
Dùng để Hàng đợi ưu tiên Tra cứu, tìm kiếm có thứ tự

Các Thuật Ngữ Quan Trọng

key: Các giá trị xác định thứ tự. Nếu lưu trữ số, các số có thể là key. Nếu lưu trữ các đối tượng phức tạp hơn, key là trường dữ liệu mà ta so sánh. Không giống như trong bảng băm, các key trong heap không nhất thiết phải duy nhất.

extract_min: Phương thức (nhanh chóng) trích xuất phần tử nhỏ nhất từ min-heap.

Ưu và Nhược Điểm

Ưu Điểm:

  • Min-heap có thể nhanh chóng trích xuất giá trị nhỏ nhất.
  • Các phép trích xuất liên tiếp từ min-heap vào một mảng sẽ tạo ra một mảng đã sắp xếp.

Nhược Điểm:

  • Không có cách thuận tiện để tìm kiếm một giá trị key cụ thể trong heap.
  • Các mục chỉ được sắp xếp một phần: phần tử nhỏ nhất (hoặc lớn nhất) luôn nằm ở gốc, nhưng vì phần còn lại không có thứ tự toàn cục nên tìm một giá trị bất kỳ vẫn là O(n). Dù vậy, khai thác khéo tính chất heap đôi khi cho phép cắt tỉa bớt không gian tìm kiếm.

Trong Phỏng Vấn: Khi Nào Nên Sử Dụng Heap?

Heap được thiết kế để thực hiện một việc cụ thể một cách hiệu quả: thực hiện các phép trích xuất tối thiểu (hoặc tối đa) liên tiếp. Các bài toán có thể khác nhau, nhưng đều có chung nhu cầu này.

Một số ví dụ điển hình:

  • Tìm khoảng cách nhỏ nhất giữa hai nút trong đồ thị
  • Lấy sự kiện được lên lịch tiếp theo
  • Theo dõi giá trị trung vị trong quá trình streaming
  • Tìm k ký tự không lặp lại đầu tiên trong một chuỗi

Bảng Thao Tác Chung

Thao Tác Mô Tả Độ phức tạp thời gian Thay đổi cấu trúc
insert(key) Chèn key vào heap O(log n) Có
extract_min() Trả về và loại bỏ mục có key nhỏ nhất O(log n) Có
peek_min() Xem key nhỏ nhất, không loại bỏ khỏi heap O(1) Không
heapify(list) Tạo heap mới từ danh sách n phần tử O(n) N/A (tạo heap)
Vì sao heapify là O(n) chứ không phải O(n log n)? Trực giác hay gặp là "n lần chèn, mỗi lần O(log n) nên tổng là O(n log n)". Nhưng cách dựng heap từ dưới lên (bottom-up, chính là heapq.heapify) rẻ hơn nhiều: phần lớn nút nằm gần đáy nên chỉ phải "chìm xuống" (sift down) rất ít bậc. Cụ thể, một nửa số nút là lá (0 thao tác), một phần tư ở độ cao 1, một phần tám ở độ cao 2, và cứ thế. Tổng công việc tỉ lệ với n nhân tổng chuỗi h/2^h, mà chuỗi này hội tụ về hằng số 2, nên toàn bộ chỉ tốn O(n). Đây là một câu hỏi phỏng vấn rất hay bị hỏi.

Stack và Queue là gì?

Stacks (ngăn xếp ) và Queues (hàng đợi) được nhóm lại với nhau vì chúng có nhiều thuộc tính giống nhau. Cả hai đều là cấu trúc dữ liệu được thiết kế để chứa các phần tử và trả về chúng theo thứ tự cụ thể. Sự khác biệt giữa các cấu trúc dữ liệu là thứ tự các mục được truy xuất.

  • Stacks là First In, Last Out / Last In, First Out:

    Hãy xem xét một chồng sách theo nghĩa đen. Khi bạn đặt một cuốn sách lên trên cùng của chồng sách, bạn phải lấy nó ra trước khi bạn có thể lấy những cuốn sách bên dưới. Cuốn sách ở dưới cùng không thể lấy được cho đến khi bạn lấy hết những cuốn sách khác ở trên cùng.

    Nếu các phần tử được thêm vào ngăn xếp theo thứ tự [A, B, C, D, E], chúng sẽ bị xóa theo thứ tự [E, D, C, B, A], giả sử tất cả các phần tử đến đều xảy ra trước khi quá trình xóa bắt đầu.

  • Queues là First In, First Out:

    Trong một hàng (hoặc hàng đợi) tại một ngân hàng, người đầu tiên đến là người đầu tiên được phục vụ. Khi sử dụng hàng đợi để lưu trữ dữ liệu, các phần tử đầu tiên vào là các phần tử đầu tiên ra.

    Nếu các phần tử được thêm vào hàng đợi theo thứ tự [A, B, C, D, E], chúng sẽ được xóa theo cùng thứ tự ([A, B, C, D, E]), ngay cả khi các lần đến và xóa được đan xen.

    Có thể bạn hình dung các phần tử "dồn lên phía trước" mỗi khi phần tử đầu bị lấy ra. Nhưng trong các triển khai hiệu quả (như deque hay mảng vòng), các phần tử còn lại không hề dịch chuyển, chỉ có con trỏ đánh dấu đầu hàng đợi di chuyển. Nhờ vậy thao tác lấy ra (dequeue) là O(1).

Do các phép ẩn dụ được sử dụng, chúng ta thường nói về "phía trên" và "phía dưới" của một ngăn xếp, nhưng lại nói về "phía trước" và "phía sau" của một hàng đợi.

Cả ngăn xếp và hàng đợi đều là các kiểu dữ liệu trừu tượng, nghĩa là chúng ta được đảm bảo có thể đưa các phần tử vào và xóa chúng theo thứ tự đã chỉ định. Bạn có thể xây dựng một ngăn xếp hoặc hàng đợi từ bất kỳ cấu trúc dữ liệu nào bạn thích, chẳng hạn như mảng hoặc danh sách được liên kết, nếu bạn cung cấp một cách để thêm các phần tử theo đúng thứ tự. Ví dụ, trong Python, danh sách chuẩn hoạt động như cả một mảng và một ngăn xếp.

Các thuật ngữ quan trọng:

Cả ngăn xếp và hàng đợi đều có thao tác thêm (đẩy/thêm vào hàng đợi) và thao tác xóa (đẩy/gỡ ra khỏi hàng đợi).

  • push (stack): Thêm đối tượng vào "đỉnh" của stack
  • pop (stack): Loại bỏ đối tượng khỏi "đỉnh" của stack
  • enqueue (queue): Thêm đối tượng vào "cuối" của queue
  • dequeue (queue): Loại bỏ đối tượng từ "đầu" của queue

Tên của các hàm có thể khác với các hàm được hiển thị ở trên, tùy thuộc vào cách bạn triển khai ngăn xếp hoặc hàng đợi và ngôn ngữ lập trình bạn sử dụng. Ví dụ, khi sử dụng danh sách Python làm ngăn xếp, sử dụng L.append(item) là lệnh đẩy, nhưng Python hỗ trợ lệnh L.pop().

Một cách triển khai khéo léo của một đối tượng vừa là ngăn xếp vừa là hàng đợi là sử dụng danh sách liên kết kép, có tham chiếu đến phần tử đầu và phần tử đuôi. Danh sách liên kết kép này có thể triển khai cả bốn hàm trên với độ phức tạp thời gian O(1).

Các thao tác chung:

Vì stack và queue là các kiểu dữ liệu trừu tượng, nên có một số tranh luận về việc liệu độ phức tạp về thời gian có phù hợp với các phương pháp hay không. Cuộc tranh luận bắt nguồn từ các câu hỏi về việc liệu việc thêm và xóa khỏi stack và queue có phải là điều duy nhất chúng phải làm (và độ phức tạp về thời gian là một chi tiết triển khai) hay liệu độ phức tạp về thời gian có phải là nội tại đối với định nghĩa của stack và queue hay không. Đối với bảng bên dưới, chúng tôi đã chọn tùy chọn thực dụng là bao gồm độ phức tạp về thời gian làm một phần của định nghĩa, vì lựa chọn sử dụng stack hoặc queue thay vì một số cấu trúc dữ liệu khác của bạn có lẽ là vì chúng hỗ trợ việc thêm và xóa nhanh dữ liệu theo thứ tự bạn muốn truy cập.

Nếu bạn đang sử dụng một cấu trúc dữ liệu đa năng như list của Python (là một stack và một queue), thay vì một queue hoặc stack được tối ưu hóa, thì hiệu suất của bạn có thể sẽ kém hơn so với chỉ định bên dưới.

Thao Tác Stack Mô Tả Độ phức tạp thời gian Thay đổi cấu trúc
push(item) Đẩy item lên "trên cùng" của ngăn xếp O(1) Có
pop() Xóa item được thêm gần đây nhất khỏi ngăn xếp. (tức là item ở "trên cùng") O(1) Có
peek() Truy cập item được thêm gần đây nhất trong ngăn xếp mà không xóa mục đó O(1) Không
isEmpty() Trả về True nếu không có mục nào trong ngăn xếp, False nếu ngược lại O(1) Không
Thao Tác Queue Mô Tả Độ phức tạp thời gian Thay đổi cấu trúc
enqueue(item) Đặt item vào cuối hàng đợi O(1) Có
dequeue() Xóa item ở đầu hàng đợi O(1) Có
peek() Truy cập item ở đầu hàng đợi mà không xóa mục đó O(1) Không
isEmpty() Trả về True nếu không có mục nào trong hàng đợi, False nếu ngược lại O(1) Không
Bẫy Python thường gặp: đừng dùng list làm queue. list.pop(0) phải dịch toàn bộ phần tử còn lại lên một chỗ nên tốn O(n); hãy dùng collections.deque với deque.popleft() chỉ O(1). (Ngược lại, dùng list làm stack thì vẫn tốt vì append() và pop() ở cuối đều là O(1).)

Ví Dụ về Heaps, Stacks và Queues Trong Python

Heap (với heapq)

import heapq

min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 7)

print("Phần tử nhỏ nhất:", heapq.heappop(min_heap))  # lấy ra min
print("Heap còn lại:", min_heap)

# Lấy 3 phần tử nhỏ nhất
print("3 nhỏ nhất:", heapq.nsmallest(3, [4, 1, 7, 3, 9, 5]))
Kết quả:
Phần tử nhỏ nhất: 3
Heap còn lại: [5, 7]
3 nhỏ nhất: [1, 3, 4]

Stack (dùng list)

stack = []
stack.append("A")
stack.append("B")
stack.append("C")

print("Đỉnh stack:", stack[-1])      # xem, không lấy ra
print("Lấy ra (pop):", stack.pop())
print("Stack còn lại:", stack)
Kết quả:
Đỉnh stack: C
Lấy ra (pop): C
Stack còn lại: ['A', 'B']

Queue (dùng collections.deque)

from collections import deque

queue = deque()
queue.append("A")
queue.append("B")
queue.append("C")

print("Đầu queue:", queue[0])                 # xem, không lấy ra
print("Lấy ra (popleft):", queue.popleft())
print("Queue còn lại:", queue)
Kết quả:
Đầu queue: A
Lấy ra (popleft): A
Queue còn lại: deque(['B', 'C'])

Cheat Sheet ôn nhanh trước phỏng vấn

Cấu trúc Nguyên tắc Thao tác chính Use case thực tế
Stack LIFO push / pop O(1) DFS, ngăn xếp lời gọi hàm (call stack), undo/redo, lịch sử trình duyệt, kiểm tra ngoặc cân bằng
Queue FIFO enqueue / dequeue O(1) BFS, hàng đợi tác vụ (job queue), message queue (RabbitMQ, Kafka consumer), điều phối request
Heap Hàng đợi ưu tiên insert / extract-min-max O(log n), heapify O(n) Dijkstra, A*, Top K phần tử, scheduler (lấy việc ưu tiên kế tiếp), theo dõi trung vị khi streaming

— Kai

Thấy bài viết hữu ích?

0 lượt thích

Đăng nhận xét