HEAP LÀ GÌ

     

Trong lập trình lúc biểu diễn tài liệu ở dạng tủ đồ (collection) thì ắt hẳn nhiều người thường quen sử những kiểu dữ liệu như list (list), tập đúng theo ( set), khóa - quý giá (dictionary), hàng ngóng ( queue). Bây giờ mình xin trình làng với các bạn kiểu dữ liệu đống (heap) - một kiểu tài liệu mà mọi tín đồ ít lúc sử dụng.

Bạn đang xem: Heap là gì

Định nghĩa về đụn (heap)

Đống (heap) là một cấu trúc dữ liệu dựa trên cây thỏa mãn nhu cầu tính hóa học đống: vào một heap về tối đa (max-heap) , đối với bất kỳ nút C đã mang lại nào , nếu p. Là nút thân phụ của C, thì khóa ( cực hiếm ) của P lớn hơn hoặc bởi khóa của C. Trong một heap buổi tối thiểu (min-heap) , khóa của P nhỏ dại hơn hoặc bằng khóa của C. Nút ngơi nghỉ "đỉnh" của heap (không có cha) được điện thoại tư vấn là nút cội .

*

Đống là 1 trong triển khai hiệu quá buổi tối đa mang đến kiểu dữ liệu trừu tượng "hàng đợi ưu tiên" (priority queues). Cùng trên thực tế kiểu tài liệu hàng đợi ưu tiên thường xuyên được gọi luôn là heaps mặc dù chúng có thể được implement theo các cách khác. Vào một đống, bộ phận ưu tiên tối đa (hoặc thấp nhất) luôn luôn nằm sống nút gốc. Tuy nhiên đống không phải là một kết cấu sắp xếp, nó có thể được coi như là 1 trong những đặt hàng một trong những phần (partially ordered). Heap là một cấu tạo dữ liệu bổ ích khi cần được loại bỏ nhiều lần đối tượng người dùng có nút ưu tiên tối đa (hoặc thấp nhất).

Xem thêm: Cavet Xe Là Gì? Cách Nhận Biết Cà Vẹt Xe Photo Công Chứng Có Bị Phạt Không ?

Đống được sử dụng nhiều độc nhất vô nhị là lô nhị phân. Đống tất cả vai trò đặc biệt quan trọng trong các thuật toán mang đến đồ thị ví dụ như thuật toán Dijkstra, tốt thuật toán thu xếp heapsort.

Các thao tác thường chạm chán trên đốngtìm-max (tìm-min): tìm kiếm khóa lớn nhất trong max-heap (tìm khóa nhỏ nhất trong đống-min).xóa-max (xóa-min): xóa nút cội của max-heap (min-heap).tăng-khóa (giảm-khóa): chuyển đổi giá trị một khóa vào max-heap (min-heap).chèn: chèn thêm 1 khóa new vào đống.hợp: phù hợp hai lô lại thành một đống mới chứa tất cả các khóa của tất cả hai.

Xem thêm: Toán Lý Sử Là Khối Gì ? Các Trường Tuyển Sinh Khối A04 Toán Sử Địa Là Khối Gì

Thời gian triển khai các phép toán trên lô nhị phân

Thao tácthời gian
tìm-maxO(1)
xóa-maxO(log n)
chènO(log n)
tăng-khóaO(log n)
hợpO(n)
Sử dụng gò trong bài toàn search k thành phần lớn nhất

Khi kiếm tìm k thành phần lớn độc nhất (hoặc bé dại nhất) trong n bộ phận cho trước rất đa số chúng ta thường thu xếp các phần tử theo máy tự nhỏ tuổi dần (hoặc tăng dần) rồi mang k phần tử đầu tiên. Mặc dù cách làm này không đạt tối ưu lúc k bé hơn nhiều đối với n. Bằng cách sử dụng kiểu dữ liệu heap nêu nghỉ ngơi trên họ sẽ kéo ra k phần tử đó mà không cần thiết phải sắp xếp các phần tử.Ví dụ về python:

Cách tuyệt dùng:

klargest = sorted(iterable, reverse=True)<:k>Cách về tối ưu:import heapqklargest = heapq.nlargest(k, iterable) Heap là kiểu tài liệu cơ bản, số đông trong các thư viện chuẩn chỉnh của các ngôn ngữ lập trình phần nhiều có.Hi vọng các các bạn sẽ sử dụng một phương pháp hiệu quả.