Extracting the top item from the heap

The extract operation extracts the maximum value from a max heap. Unlike the peek operation, it also deletes the node with the maximum value from the heap. The implementation is encapsulated in the extract function that deletes the root node in the binary tree and returns its value while ensuring that the resulting binary tree is still a heap. Let us look at the algorithm and implementation of the extract operation on a max heap implemented as an array.

Algorithm

The algorithm for extracting the maximum value in a max-heap is very simple. It combines peek and delete operations. We copy the value at the tree's root node to return it later and then delete the root node using the delete operation. The delete operation ensures that the resulting binary tree still follows the heap property and remains a heap.