define

Maximum heap: for any node, its children are not larger than the node. Minimum heap: for any node, its children are not smaller than the node

features

Maximum heap: the top node is always the largest in the heap. Minimum heap: the top node is always the smallest in the heap

Graph (with maximum heap as an example)

Figure 1.1 a maximum heap


Figure 1.2 Inserting a new node into the maximum heap, the new node is larger than its parent and needs to be swapped

Figure 1.3 The new node is still larger than its parent and needs to be switched again

Figure 1.4 At this point, the new node is no larger than its parent node, and the insertion operation is complete

Figure 1.5 Maximum heap after insertion


Figure 1.6 Swap the top node with the last node in the heap, and remove the top node to be removed. The new top node is smaller than its node, so it needs to swap places

Figure 1.7 The node is still smaller than the child node after it switches positions with its larger child node, so it needs to continue to switch positions

Figure 1.8 At this point, no child node is larger than this node. The operation ends

Figure 1.9 Retaining the maximum heap after the extraction operation

Time complexity

Insert new node: O(log⁡2n)O(\ log_2N)O(log2n) Remove top node: O(log⁡2n)O(\ log_2N)O(log2n)