Heap

Algorithms
heap
Catalogue
  1. 1. Basic
    1. 1.1. Definition
    2. 1.2. Operation
    3. 1.3. Python Lib
  2. 2. LintCode 544. Top k Largest Numbers
    1. 2.1. Sol1. Sort
    2. 2.2. Sol2. Min heap
    3. 2.3. Sol3. Max heap
    4. 2.4. Sol4. Quick Partition
  3. 3. 218. The Skyline Problem
  4. 4. 857. Minimum Cost to Hire K Workers

Heap, also called “Priority Queue”

Basic

Definition

  • value in any node is less than its decendent and root is the least element
  • complete binary tree
  • Max Heap means root is maximum element, Min Heap means root is minimum element
  • unsorted bu follow rules above

Operation

  • insert, put the element in the last and swap up, O(logn)
  • update, O(logn)
  • get/top, get the root element, O(1)
  • pop, delete the root element, O(logn) put the last element to the root
  • heapify: transform unsorted array to a heap, O(n)

Python Lib

  • min heap
  1. heapq.heapify(iterable), O(c * n)
    This function is used to convert the iterable into a heap data structure. i.e. in heap order.
  2. heapq.heappush(heap, ele), O(logn)
    This function is used to insert the element mentioned in its arguments into heap. The order is adjusted, so as heap structure is maintained.
  3. heapq.heappop(heap), O(logn)
    This function is used to remove and return the smallest element from heap. The order is adjusted, so as heap structure is maintained.
  4. heapq.heappushpop(heap, ele)
    This function combines the functioning of both push and pop operations in one statement, increasing efficiency. Heap order is maintained after this operation.
  5. heapq.heapreplace(heap, ele)
    This function also inserts and pops element in one statement, but it is different from above function. In this, element is first popped, then element is pushed.i.e, the value larger than the pushed value can be returned.
  6. heapq.nlargest(k, iterable, key = fun)
    This function is used to return the k largest elements from the iterable specified and satisfying the key if mentioned.
  7. heapq.nsmallest(k, iterable, key = fun)
    This function is used to return the k smallest elements from the iterable specified and satisfying the key if mentioned.
1
import heapq

LintCode 544. Top k Largest Numbers

Sol1. Sort

  • Time : O(nlogn)
    1
    2
    3
    class Solution:
        def topk(self, nums, k):
            return sorted(nums)[-k:][::-1]

Sol2. Min heap

  • Time : O(k + (n-k)logk)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import heapq
class Solution:
    def topk(self, nums, k):
        heap = []

        # Heapify k elements, O(k)
        heap = heapq.heapify(nums[:k])
        #for i in xrange(k):
        #    heapq.heappush(heap, nums[i])

        # Keep pop out n-k elements, O((n-k)logk)
        n = len(nums)
        for i in xrange(k, n):
            heapq.heappush(heap, nums[i])
            heapq.heappop(heap)

        return sorted(heap, reverse=True)

Sol3. Max heap

  • Time : O(n + klog(n))
  • Step1. Heapify, O(n)
  • Step2. pop k elements, O(klogn)

Sol4. Quick Partition

  • Time : Amortized O(n), Worst Case : O(n^2)

218. The Skyline Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def getSkyline(self, buildings):
        positions = set([b[0] for b in buildings] + [b[1] for b in buildings])
        res = [[0, 0]]
        live = []
        i = 0
        for p in sorted(positions):
            # Keep all the position before p to the heap "live"
            while i < len(buildings) and buildings[i][0] <= p:
                heapq.heappush(live, (-buildings[i][2], buildings[i][1]))
                i += 1

            # Keep the maximum height's position > p
            while live and live[0][1] <= p:
                heapq.heappop(live)

            h = -live[0][0] if live else 0
            if h != res[-1][1]:
                res.append([p, h])
        return res[1:]

857. Minimum Cost to Hire K Workers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def mincostToHireWorkers(self, quality, wage, K):
        workers = sorted([(float(w)/q, q) for q, w in zip(quality, wage)])

        pool = []
        qsum = 0
        res = float('inf')
        for r, q in workers:
            heapq.heappush(pool, -q)
            qsum += q
            if len(pool) > K:
                qsum += heapq.heappop(pool)

            if len(pool) == K:
                res = min(res, r * qsum)
        return res
Share