Implementing and understanding the properties of min-heaps and max-heaps.
A heap is a complete binary tree that satisfies the heap property. This property defines the relationship between a parent node and its children. There are two main types of heaps: Max-Heap and Min-Heap. In a Max-Heap, the value of each node is greater than or equal to the value of its children. This means the largest element in the heap is always at the root. Conversely, in a Min-Heap, the value of each node is less than or equal to the value of its children, making the smallest element accessible at the root. This property of providing constant-time access to the min or max element is what makes heaps so powerful. While heaps are tree structures, they are commonly implemented using arrays for efficiency. For a node at index `i`, its left child is at index `2*i + 1`, its right child is at `2*i + 2`, and its parent is at `floor((i-1)/2)`. This array-based implementation avoids the overhead of pointers and improves cache performance. The core operations, 'insert' and 'extract-min/max', involve adding an element to the end of the array and then 'bubbling' it up or replacing the root with the last element and 'sinking' it down to maintain the heap property, both in O(log n) time.