Authored by Tony Feng
Created on March 28th, 2022
Last Modified on March 28th, 2022
Understanding Heaps
Main Concepts
- Heaps are complete binary trees. Complete binary trees satisfy the following conditions:
- All levels are filled, except the last.
- All the nodes are as far left as possible.
- The root of every subtree should be the greatest or smallest element in the subtree, recursively.
- Minheap: The root of every subtree is the smallest element.
- Maxheap: The root of every subtree is the largest element.
- Heapify: From an array to a heap, the solution is unique and the time complexity is O(N). (Formal Proof)
Applications of Heaps
- Priority Queues
- The root of a heap always contains the maximum or the minimum value, based on the heap type.
- The element with the highest/lowest priority can be retrieved in O(1) time.
- Statistics
- If we want the kth smallest or largest element, we can pop the heap k times to retrieve them.
- Graph Algorithms
- e.g. Dijkstra’s algorithm, Prim’s algorithm.
Operations
- Search
- For the top of heap, it’s O(1)
- The rest are O(N)
- Insert - O(log(N))
- Delete - O(log(N))
Set Implementation in Python
|
|
Set Implementation in Java
|
|
Reference
- Using the Heap Data Structure in Python
- 堆删除操作逻辑
- GreeksforGreeks - Time Complexity of building a heap
- 手把手带你刷Leetcode力扣 - 集合 Set
- 手把手带你刷Leetcode力扣 - Python3集合常用操作
- 手把手带你刷Leetcode力扣 - Java集合常用操作