|
| Cấu Trúc Dữ liệu: Heaps, Stacks, Queues |
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.
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.
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 được sắp xếp một phần; việc sử dụng thông minh tính chất heap có thể cho phép một số cắt tỉnh 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
kký 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) |
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.
(Hoạt ảnh gợi ý rằng các phần tử trong hàng đợi "di chuyển về phía trước" khi phần tử đầu tiên bị xóa. Trong các triển khai hàng đợi hiệu quả, các phần tử không rời khỏi hàng đợi sẽ ở nguyên vị trí, do đó, việc hủy hàng đợi có thể được triển khai dưới dạng hoạt động
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 hàng đợi, 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 |
|---|---|---|---|
enque(item) |
Đặt itemvào cuối hàng đợi |
O(1) |
Có |
pop() |
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 |
Ví Dụ về Heaps, Stacks và Queues Trong Python
import heapq
# Heap Example
def heap_examples():
# Min Heap using heapq
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 7)
print("Min Heap Operations:")
print("Smallest element:", heapq.heappop(min_heap)) # Removes and returns smallest
print("Remaining heap:", min_heap)
# Finding k smallest elements
numbers = [4, 1, 7, 3, 9, 5]
k_smallest = heapq.nsmallest(3, numbers)
print("3 Smallest elements:", k_smallest)
# Demonstrate all operations
def main():
heap_examples()
if __name__ == "__main__":
main()# Stack Example using list
def stack_examples():
stack = []
# Push operations
stack.append(1)
stack.append(2)
stack.append(3)
print("\nStack Operations:")
print("Top of stack:", stack[-1]) # Peek
print("Popped item:", stack.pop()) # Remove top item
print("Updated stack:", stack)
# Demonstrate all operations
def main():
stack_examples()
if __name__ == "__main__":
main()from collections import deque
# Queue Example using deque
def queue_examples():
queue = deque()
# Enqueue operations
queue.append(1)
queue.append(2)
queue.append(3)
print("\nQueue Operations:")
print("Front of queue:", queue[0]) # Peek
print("Dequeued item:", queue.popleft()) # Remove first item
print("Updated queue:", queue)
# Demonstrate all operations
def main():
queue_examples()
if __name__ == "__main__":
main()import heapq
from collections import deque
# Heap Example
def heap_examples():
# Min Heap using heapq
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 7)
print("Min Heap Operations:")
print("Smallest element:", heapq.heappop(min_heap)) # Removes and returns smallest
print("Remaining heap:", min_heap)
# Finding k smallest elements
numbers = [4, 1, 7, 3, 9, 5]
k_smallest = heapq.nsmallest(3, numbers)
print("3 Smallest elements:", k_smallest)
# Stack Example using list
def stack_examples():
stack = []
# Push operations
stack.append(1)
stack.append(2)
stack.append(3)
print("\nStack Operations:")
print("Top of stack:", stack[-1]) # Peek
print("Popped item:", stack.pop()) # Remove top item
print("Updated stack:", stack)
# Queue Example using deque
def queue_examples():
queue = deque()
# Enqueue operations
queue.append(1)
queue.append(2)
queue.append(3)
print("\nQueue Operations:")
print("Front of queue:", queue[0]) # Peek
print("Dequeued item:", queue.popleft()) # Remove first item
print("Updated queue:", queue)
# Demonstrate all operations
def main():
heap_examples()
stack_examples()
queue_examples()
if __name__ == "__main__":
main()