DAA - Phương pháp trích xuất

Phương pháp trích xuất được sử dụng để trích xuất phần tử gốc của một Heap. Sau đây là thuật toán.

Algorithm: Heap-Extract-Max (numbers[]) 
max = numbers[1] 
numbers[1] = numbers[heapsize] 
heapsize = heapsize – 1 
Max-Heapify (numbers[], 1) 
return max

Thí dụ

Chúng ta hãy xem xét cùng một ví dụ đã thảo luận trước đây. Bây giờ chúng ta muốn trích xuất một phần tử. Phương thức này sẽ trả về phần tử gốc của heap.

Sau khi xóa phần tử gốc, phần tử cuối cùng sẽ được chuyển đến vị trí gốc.

Bây giờ, hàm Heapify sẽ được gọi. Sau Heapify, heap sau được tạo.