Heaps: Difference between revisions
(Created page with " '''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...") |
No edit summary |
||
| Line 6: | Line 6: | ||
There are two main 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 == | == Operations == | ||
| Line 15: | Line 15: | ||
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. | 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 === | === 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. | 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 === | === Peek === | ||
To retrieve the highest-ranked element without removing it, the root element of the heap is returned. | To retrieve the highest-ranked element without removing it, the root element of the heap is returned. | ||
* Time complexity: O(1) | |||
=== Heapify === | === 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. | 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 == | == Applications == | ||
| Line 36: | Line 36: | ||
Heaps are commonly used in the following 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 == | == 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 == | == See Also == | ||
* [[:Category:Data_Structures|Data Structures]] | |||
* [[:Category:Algorithms|Algorithms]] | |||
[[category:Heap]] | [[category:Heap]] | ||
Latest revision as of 00:36, 13 May 2023
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[edit]
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[edit]
Insertion[edit]
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[edit]
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[edit]
To retrieve the highest-ranked element without removing it, the root element of the heap is returned.
- Time complexity: O(1)
Heapify[edit]
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[edit]
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[edit]
- Implementing a priority queue
- K-th largest element in an array
- Merge k sorted lists
- Median in a data stream