Phần này trình bày cách gộp hai list đã sắp xếp bằng module heapq trong Python. Ví dụ: list1 = [10, 20, 30, 40] và list2 = [100, 200, 300, 400, 500], sau khi gộp sẽ ra list3 = [10, 20, 30, 40, 100, 200, 300, 400, 500].
Module heapq là thư viện chuẩn, cần import trước khi dùng:
import heapq
Các phương thức chính của heapq
- heapq.heapify(iterable): Chuyển iterable thành cấu trúc heap.
- heapq.heappush(heap, element): Chèn phần tử vào heap và heapify lại.
- heapq.heappop(heap): Lấy và xóa phần tử gốc (nhỏ nhất), heapify phần còn lại.
- heapq.heappushpop(heap, element): Chèn và lấy phần tử gốc trong một câu lệnh.
- heapq.heapreplace(heap, element): Lấy phần tử gốc rồi chèn phần tử mới.
- heapq.nlargest(n, iterable, key=None): Trả về n phần tử lớn nhất.
- heapq.nsmallest(n, iterable, key=None): Trả về n phần tử nhỏ nhất.
Ví dụ code
import heapq
first_list = [45, 12, 63, 95, 74, 21, 20, 15, 36]
second_list = [42, 13, 69, 54, 15]
first_list = sorted(first_list)
second_list = sorted(second_list)
print('First sorted list: ' + str(first_list))
print('Second sorted list: ' + str(second_list))
final_list = list(heapq.merge(first_list, second_list))
print('The final list: ' + str(final_list))
Kết quả
First sorted list: [12, 15, 20, 21, 36, 45, 63, 74, 95] Second sorted list: [13, 15, 42, 54, 69] The final list: [12, 13, 15, 15, 20, 21, 36, 42, 45, 54, 63, 69, 74, 95]
Lưu ý: heapq.merge() yêu cầu các list đầu vào đã được sắp xếp. Nó trả về iterator, nên cần list() để materialize.