What is a heap (in the context of data structures)?

Heap — a specialized tree used as a data structure. The main property of a heap is partial ordering: for any node, the condition that the value of the parent node is greater than or equal to the value of any of its children (max-heap) or less than or equal to (min-heap) is maintained.

Key characteristics:

• Binary tree: Most often implemented as a binary tree, where each node has no more than two children.
• Complete binary tree: All levels, except possibly the last, are fully filled. Nodes on the last level are filled from left to right. This allows efficient storage of the heap as an array.
• Heap property:
  • Max-heap: The value of each node is greater than or equal to the values of its children. The maximum element is always at the root.
  • Min-heap: The value of each node is less than or equal to the values of its children. The minimum element is always at the root.

Main operations with a heap:

• Insert element: Adding a new element and maintaining the heap property.
• Remove element: Removing the root element (maximum or minimum depending on the heap type) and maintaining the heap property.
• Create heap: Building a heap from an array of elements.

Applications of heap:

• Sorting: Heap sort algorithm.
• Priority queues: Efficient implementation of queues where elements are processed in order of priority.
• Search algorithms: For example, finding the k-th largest element.
• Graph algorithms: For example, Dijkstra's algorithm.

Representation of a heap as an array:

Since a heap is a complete binary tree, it can be efficiently stored in an array without using pointers.

• If a node is at index i, its left child is at index 2*i + 1.
• Its right child is at index 2*i + 2.
• Its parent is at index (i - 1) / 2.

# Example of representing a min-heap as an array
heap_array = [10, 15, 20, 17, 25, 30]

# Root: heap_array[0] = 10
# Left child of root: heap_array[2*0 + 1] = heap_array[1] = 15
# Right child of root: heap_array[2*0 + 2] = heap_array[2] = 20
# Parent of element at index 3 (17): heap_array[(3-1)//2] = heap_array[1] = 15