Review: Heap Problems

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:

1. It may be represented by using an array, which is space-efficient.
2. The children of the node at position n would be at positions 2n + 1 and 2n + 2 in a zero-based array.
3. From child to parent: n -> (n-1)/2

Complexity:

1. Insert an element to binary heap. Time O(log(n))
2. Remove the top from binary heap. Time O(log(n))
3. 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:

• Heap queue (or heapq) in Python
• How to use Queue: A beginner’s guide

See more blog_posts.