What is the difference between a min-heap and a max-heap?

A min-heap is a binary tree where each parent node is less than or equal to its child nodes, while a max-heap is the opposite.

A min-heap and a max-heap are both specialised tree-based data structures that satisfy the heap property. They are both binary trees, meaning each node has at most two children. However, the key difference lies in how the nodes are organised in relation to their parent nodes.

In a min-heap, the value of each parent node is less than or equal to the values of its child nodes. This means that the smallest (minimum) element is always at the root of the tree. Whenever elements are inserted or removed, the tree reorganises itself to ensure this property is maintained. This makes min-heaps particularly useful for algorithms that need to quickly find or remove the smallest element, such as Dijkstra's algorithm for finding the shortest path in a graph.

On the other hand, in a max-heap, the value of each parent node is greater than or equal to the values of its child nodes. This means that the largest (maximum) element is always at the root of the tree. Like min-heaps, max-heaps reorganise themselves whenever elements are inserted or removed to ensure this property is maintained. Max-heaps are useful for algorithms that need to quickly find or remove the largest element, such as the heapsort algorithm for sorting elements in order.

Both min-heaps and max-heaps can be implemented using an array, where each element in the array represents a node in the tree and the parent-child relationship is determined by the indices of the elements. This makes heaps efficient in terms of memory usage, as they do not require any additional pointers or data structures to maintain their structure. Understanding the array implementation of heaps is crucial in mastering fundamental computer operations.

A-Level Computer Science Tutor Summary: A min-heap is a binary tree where parent nodes are smaller than their children, making it easy to find the smallest element. A max-heap is the opposite, with parent nodes larger than their children, helping to find the largest element. Both are efficient for different algorithms and can be implemented using arrays.