Trong nhiều ứng dụng, chúng ta cần thực hiện nhanh chóng một số thao tác, chẳng hạn như truy vấn và trích xuất giá trị tối đa hoặc tối thiểu trong dữ liệu. Ví dụ: khi cần sắp xếp điểm kiểm tra của học sinh, chúng ta có thể phải thường xuyên tìm và trích xuất điểm cao nhất hoặc thấp nhất. Ngoài ra, yêu cầu này còn tồn tại rộng rãi trong việc lập kế hoạch ưu tiên và xử lý luồng dữ liệu.

Giả sử chúng tôi muốn giải quyết một vấn đề: có một tập hợp mà mỗi thao tác có thể thêm dữ liệu hoặc truy xuất giá trị lớn nhất từ ​​đó chúng ta nên làm gì? Sẽ cần duyệt qua tập dữ liệu thường xuyên (giá trị là \(O(n)\)). phải lặp lại truy vấn kiểu này nhiều lần. hiệu quả, mang lại hiệu quả tốt hơn. về thời gian \(O(\log n)\), giải quyết vấn đề về toàn bộ mảng trong phương pháp brute Force.

Phân tích nhị phân là gì?

Heap nhị phân là một loại cây nhị phân đặc biệt (Cây nhị phân), được chia thành heap lớn và heap nhỏ dành cho số:

• Max Maximum) này.
• Tối thiểu heap) này.

Cấu hình dữ liệu này đặc biệt phù hợp với các vấn đề thường xuyên Thực hiện các truy vấn giá trị tối đa hoặc tối thiểu. trên, tất nhiên phải sử dụng một gốc lớn nhất.

          50 / \ 30 40 / \ / \ 10 20 35 25

Tại sao nên sử dụng mảng để xây dựng phân tích nhị phân chồng chéo?

Phân tích nhị phân thường được phát triển bằng cách sử dụng một mảng (Array) thay vì danh sách liên kết:

1. Việc phát triển mảng giúp loại bỏ nhu cầu có thêm không gian trong danh sách liên kết để lưu trữ con trỏ.
2. cây nhị phân phân tích đặc biệt và đầy đủ như vậy phù hợp hơn cho việc lưu trữ mảng.

Nếu nút gốc được đặt thành \(0\) và nút ở vị trí \(i\), thì nút bên trái của nó ở vị trí \(2i+1\) và nút con bên phải của nó ở vị trí \(2i +2\) , nút cha nằm ở \(\lfloor(i-1)/2\rfloor\). \(i\)th thì nút bên trái của nó ở vị trí \(2i\), nút bên phải ở vị trí \( 2i+1\) và nút gốc nằm ở\(\lfloor i/2\rfloor \).

Khi xây dựng vùng heap, ước tính là thao tác trực tiếp trên mảng ban đầu, coi mảng ban đầu là phân vùng nhị phân và điều chỉnh vùng heap Mảng đó phù hợp với các thuộc tính của vùng heap. để đảm bảo trật tự trên đường dẫn này. array failed.

#bao gồm  #bao gồm  use no std namespace void heapify(vector& heap, int n, int i) { int lớn nhất = i; if (trái < n && heap[left] > heap[lớn nhất]) { lớn nhất = left } if (phải < n &&) heap[right] > heap[lớn nhất]) { lớn nhất = đúng; } if (lớn nhất != i) { swap(heap[i], heap[lớn nhất]); heapify(heap, n, lớn nhất & heap) { int n = heap.size( ); cho (int i = n / 2 - 1; i >= 0; --i) { đống hóa(đống, n, i);

Độ phức tạp của quá trình xử lý thời gian: \(O(n)\). Nhưng nhưng nhưng nhưng nhưng trên thực tế, bằng cách điều chỉnh heapify từng lớp bắt đầu từ nút không phải lá cuối cùng, phức tạp về tổng thời gian có thể là \(O(n)\). giảm dần theo từng lớp nên số lượng nút trong mỗi lớp giảm theo cấp số nhân. \(O(n)\), không phải \(O(n \log n)\).

Hoạt động heap: chèn (đẩy) và xóa (pop)

1. Xây dựng đống đổ nát

Quay lại đầu trang một đoạn mã nhị phân chồng lên trên phương pháp thực thi có thể được tìm thấy.

2. Thao tác chèn: đẩy

Khi chèn một phần tử mới, chúng ta cần thêm phần tử đó vào mảng cuối cùng, sau đó duy trì các thuộc tính của heap bằng cách bắt đầu từ nó và điều chỉnh lên trên:

đẩy khoảng trống (vectơ& heap, int value) { heap.push_back(value); int i = heap.size() - 1; while (i != 0 && heap[(i - 1) / 2] < heap[i]) { hoán đổi (đống[i], đống[(i - 1) / 2]); i = (i - 1) / 2;

• bộ xử lý thời gian phức tạp: \(O(\log n)\), vì chiều cao của heap là \(\log n\), tối đa cần phải điều chỉnh tăng lên \(\log n\) Hạng hai.

3. Thao tác xóa: Pop

đống đống nút gốc và xóa nút cuối cùng (nếu không sử dụng vectơ, cần thêm n để lưu công việc sử dụng tại mảng dài), sau đó khôi phục các thuộc tính của vùng heap bằng cách điều chỉnh xuống một lần:

int pop(vectơ& heap) { if (heap.empty()) return -1; // Trường hợp lỗi int root = heap[0] = heapify(heap, heap.size(), 0); return root }

Tất nhiên, bạn cũng có thể bắt đầu từ nút đã xóa và điều chỉnh lên trên, cuối cùng xóa nút cuối cùng.

• bộ xử lý thời gian phức tạp: \(O(\log n)\).Hoạt động điều chỉnh liên kết đến đường đi xuống cây.

Vì việc bổ sung và xóa luôn được thực hiện ở mảng cuối cùng nên cây sẽ luôn duy trì mật khẩu hoàn chỉnh dạng nhị phân cây cao để đảm bảo rằng chiều cao của cây là khoảng \(\log n\).

---

Open width architecture

1. Những vấn đề kinh điển mà heap có thể giải quyết

Đống được sử dụng rộng rãi trong thiết kế thuật toán và các chức năng của chúng giải quyết nhiều vấn đề kinh điển:

• Vấn đề hối tiếc và tham lam: Trong một số thuật toán tham lam, kết quả của việc lựa chọn có thể được điều chỉnh linh hoạt thông qua vùng heap.
• Thuật toán Dijkstra: Tối ưu hóa hoạt động duy trì hàng đợi ưu tiên trong thuật toán đường đi ngắn nhất một nguồn.
• Mã hóa Huffman: Xây dựng cây mã hóa tiền tố tối ưu sử dụng min-heap.
• vấn đề trung vị động: Sử dụng hai đống để duy trì các phần tử nhỏ hơn và lớn hơn tương ứng.
• Hợp nhất đa kênh \(k\) danh sách liên kết có thứ tự: Sử dụng min-heap để tìm nhanh phần tử đầu nhỏ nhất trong mỗi thao tác.

2. Các biến thể khác của heap

Heap nhị phân chỉ là một loại heap có hiệu quả vừa phải và cách thực hiện đơn giản, nhưng nó không hỗ trợ các hoạt động hợp nhất. Ý tưởng cơ bản về heap đã được mở rộng thành nhiều biến thể nâng cao khác, mỗi biến thể phù hợp với các tình huống cụ thể:

• Đống xiên: Thực hiện đơn giản và hỗ trợ hợp nhất hiệu quả.
• Đống cánh tả: Tăng tốc các hoạt động hợp nhất bằng cách duy trì độ lệch.
• Đống nhị thức: Gồm một dãy cây nhị thức, thích hợp cho việc hợp nhất dữ liệu quy mô lớn.
• Đống Fibonacci: Được sử dụng để tối ưu hóa các hoạt động thư giãn trong các thuật toán như của Dijkstra.
• Ghép nối đống: Nâng cao hiệu quả thực tế bằng cách đơn giản hóa các hoạt động.
• Hàng đợi tìm kiếm ưu tiên: Hỗ trợ heap mở rộng cho các cặp khóa-giá trị.

3. Mối quan hệ giữa heap và hàng đợi ưu tiên

Hàng đợi ưu tiên đề cập đến một hàng đợi có thể được xếp vào hàng đợi và xếp hàng theo mức độ ưu tiên và vùng heap là một trong những cấu trúc dữ liệu cốt lõi triển khai hàng đợi ưu tiên điển hình. Các hoạt động chính của hàng đợi ưu tiên (chèn, lấy giá trị tối đa/tối thiểu) đều có thể đạt được độ phức tạp về thời gian hiệu quả thông qua vùng heap và nhiều ngôn ngữ có các hoạt động vùng heap tích hợp sẵn:

• C++: sử dụng std::priority_queue, mặc định là vùng gốc lớn, vùng gốc nhỏ yêu cầu một bộ so sánh tùy chỉnh.

  #bao gồm  std::priority_queue maxHeap; // Vùng nhớ gốc lớn std::priority_queue, std::Greater> minHeap;
  

• Python: sử dụng đống q Mô-đun, mặc định là vùng gốc nhỏ.

  import heapq heap = [] heapq.heappush(heap, value) # Chèn nhỏ nhất = heapq.heappop(heap) # Lấy giá trị nhỏ nhất
  

• Java: sử dụng Hàng đợi ưu tiên, mặc định là vùng gốc nhỏ.

  PriorityQueue minHeap = new PriorityQueue<>(); PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());
  

• Đi: sử dụng thùng chứa/đống Cái túi.

  nhập "container/heap"
  

Bằng cách nắm vững các phương pháp triển khai này, hàng đợi ưu tiên phù hợp với các tình huống cụ thể có thể được xây dựng nhanh chóng bằng các ngôn ngữ khác nhau để đạt được hiệu quả xử lý dữ liệu.

Cuối cùng, bài viết giải thích chi tiết về cấu trúc và hoạt động của heap nhị phân kết thúc tại đây. Nếu bạn muốn biết thêm về giải thích chi tiết về cấu trúc và hoạt động của heap nhị phân, vui lòng tìm kiếm bài viết CFSDN hoặc tiếp tục duyệt các nội dung liên quan. Tôi hy vọng bạn sẽ ủng hộ nó trong tương lai! .