heap is a specialized tree-based data structure. Heap is useful to implement a priority queue.
Key operations: find-min, get-min, insert, etc.
Binary heaps:
- It may be represented by using an array, which is space-efficient.
- The children of the node at position n would be at positions 2n + 1 and 2n + 2 in a zero-based array.
- From child to parent: n -> (n-1)/2
Complexity:
- Insert an element to binary heap. Time O(log(n))
- Remove the top from binary heap. Time O(log(n))
- Remove an item by value. Time O(n)
## Blog link: https://code.dennyzhang.com/sliding-window-median def heapRemove(self, l, item): k = -1 for i in range(len(l)): if l[i] == item: k = i break if k != -1: l[k] = l[0] heapq.heappop(l) heapq.heapify(l) return True return False
See all heap problems: #heap
- Review: Heap Problems
- LintCode: Second Max of Array
- LintCode: Number of restaurants
- Leetcode: Trapping Rain Water II
- Leetcode: Top K Frequent Words
- Leetcode: Top K Frequent Elements
- Leetcode: Third Maximum Number
- Leetcode: Sort Characters By Frequency
- Leetcode: Network Delay Time
- Leetcode: Kth Largest Element in an Array
- Leetcode: Kth Largest Element in a Stream
- Leetcode: K Closest Points to Origin
- Leetcode: Design Twitter
Useful Link:
See more blog_posts.
Share It, If You Like It.