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

Useful Link:

See more blog_posts.

linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.