Heaps

Heap is a specialized tree-based data structure that satisfies the heap property, which is a partial ordering of elements in a tree. It is used to efficiently access the highest- or lowest-ranked elements within a dataset. Heaps are commonly implemented as binary trees and can be visualized as almost complete trees with nodes filled from top to bottom and left to right.

Types of Heaps

There are two main types of heaps:

• Max-heap: In a max-heap, the parent nodes have a greater value than their children. The largest element is at the root of the heap.

• Min-heap: In a min-heap, the parent nodes have a smaller value than their children. The smallest element is at the root of the heap.

Operations

Insertion

To insert an element into a heap, the element is first added at the end of the heap, and then the heap property is restored by "bubbling up" the element to its correct position.

• Time complexity: O(log n)

Deletion

To delete the highest-ranked element (maximum in max-heap or minimum in min-heap), the root element is removed, and the last element in the heap is moved to the root. Then, the heap property is restored by "bubbling down" the element to its correct position.

• Time complexity: O(log n)

Peek

To retrieve the highest-ranked element without removing it, the root element of the heap is returned.

• Time complexity: O(1)

Heapify

To transform an unordered array into a valid heap, the "heapify" operation is performed. Heapify processes the array elements in reverse order and ensures that the heap property is satisfied for each element.

• Time complexity: O(n)

Applications

Heaps are commonly used in the following applications:

• Implementing priority queues
• Finding the k-th largest or smallest element in a dataset
• Sorting algorithms, such as heapsort

Example Heaps Problems

• Implementing a priority queue
• K-th largest element in an array
• Merge k sorted lists
• Median in a data stream

See Also

• Data Structures
• Algorithms