堆 Heap

Idea

辅助运算Sift-up 。主要思想：就是不断的和父节点比，直到为根节点或比父节点小时停止
- 如果比父节点大，就互相替换，继续往上比。 O(logn)
辅助运算Sift-down。主要思想：就是不断的和子节点比，直到为叶子节点或比子节点都大时停止
- 如果比子节点小，就替换一个较大的子节点（左右相比），继续往下比。 O(logn)
insert(H,x)：插入元素x到堆H中。插入元素到堆尾，然后调用辅助运算Sift-up。 O(logn)
delete(H,i)。删除当前元素，将堆尾元素替上来，然后辅助运算Sift-down。 O(logn)
delete-max(H)。删除根元素。O(logn)
make-heap(A): 从数组A创建堆。
- 方法1：从一个空堆开始，逐步插入A中的每个元素。O(nlogn)
- 方法2：遍历【n/2】->【1】，每个都要遍历Sift-down(A[i])，使以A[i]为根节点的子树调整成为堆。 O(nlogn) 比方法1略微划算一些

P Implementation

def heapify(nums):
	for i in range((len(nums) + 1)//2 -1, -1, -1):
    maxHeapTop(nums, i)
def maxHeapTop(nums, i):
  # TODO

heapq.heapify(nums) # in-place update
- build heap
heapq.heappush(heapNums, a)
- append a to the tail of list nums, and execute shiftup(nums, len(nums)-1)
heapq.heappop(heapNums)
- pop the smallest element from nums
heapq.heapreplace(heapNums, a)
- pop the smallest element from nums and push a inside
heapq.heappushpop(heapNums, item)

Push item on the heap, then pop and return the smallest item from the heap.

sample

857 Minimum Cost to Hire K Workers

857. 雇佣 K 名工人的最低成本

有 n 名工人。给定两个数组 quality 和 wage ，其中，quality[i] 表示第 i 名工人的工作质量，其最低期望工资为 wage[i] 。

现在我们想雇佣 k 名工人组成一个 工资组*。*在雇佣一组 k 名工人时，我们必须按照下述规则向他们支付工资：

对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。

工资组中的每名工人至少应当得到他们的最低期望工资。

给定整数 k ，返回 组成满足上述条件的付费群体所需的最小金额 。与实际答案误差相差在 10-5 以内的答案将被接受。

Solutions:

After determining the wage based on a worker, we can find the other workers who satisfy rule 1&2: the wage must be in the ratio of wage compared to other workers, also should be larger than the minimum wage of the worker.
How to find other worker who can be satisfied efficiently? We can calculate a ratio r = minWage/quality, so that the wokers with r less than current woker's r can be satisfied.
1. let's say current base woker's quality is q1, minW1. For the wokerX with qX and minWX.
  1. If the minW1/q1 > minWX/qX, then the wage assigned to wokerX will be minW1*qX/q1 > minWx
Thus we only need to find the k wokers with r less than the current r.
How to calculate the total wage needed? Assuming that we have qualitySum of current k wokers, we can tell the total wage by qualitySum*r1 = sum of q1*minW1/q1 + q2*minW1/q1 + ... + qk*minW1/q1
How to find the k wokers with r less than current r? Max-Heap. (为什么叫最大堆？)

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        pairs = sorted(zip(quality, wage), key=lambda p: p[1] / p[0])  # 按照 r 值排序
        h = [-q for q, _ in pairs[:k]]  # 加负号变成最大堆
        heapify(h)
        sum_q = -sum(h)
        ans = sum_q * pairs[k - 1][1] / pairs[k - 1][0]  # 选 r 值最小的 k 名工人
        for q, w in pairs[k:]:  # 后面的工人 r 值更大，但是 q 也许比当前的堆顶更小
            if q < -h[0]:  # 但是 sum_q 可以变小，从而可能得到更优的答案
                sum_q += heapreplace(h, -q) + q  # 更新堆顶和 sum_q
                ans = min(ans, sum_q * w / q)
        return ans

Codes

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if k == 0:
            return []
        heaplist = HeapList()
        heaplist.buildHeap(arr[:k])
        for i in arr[k:]:
            if i < heaplist.heaplist[1]:
                heaplist.delMax()
                heaplist.insert(i)
        return heaplist.heaplist[1:]

class HeapList():
    """
    大顶堆
    """
    def __init__(self):
        self.heaplist = [0]
        self.size = 0

    def buildHeap(self, alist):
         i = len(alist) // 2
         self.size = len(alist)
         self.heaplist += alist[:]
         while i > 0:
             self.percDown(i)
             i -= 1

    def delMax(self):
        """删除堆顶最大元素"""
        retval = self.heaplist[1]
        self.heaplist[1] = self.heaplist[self.size]
        self.size -= 1
        self.heaplist.pop()
        self.percDown(1)
        return retval

    def insert(self, k):
        self.heaplist.append(k)
        self.size += 1
        self.percUP(self.size)

    def percUP(self, i):
        while i // 2 > 0:
            if self.heaplist[i] > self.heaplist[i // 2]:
                self.heaplist[i], self.heaplist[i // 2] = self.heaplist[i // 2], self.heaplist[i]
            i //= 2

    def percDown(self, i):
        while i * 2 <= self.size:
            mc = self.maxChild(i)
            if self.heaplist[i] < self.heaplist[mc]:
                self.heaplist[i], self.heaplist[mc] = self.heaplist[mc], self.heaplist[i]
            i = mc

    def maxChild(self, i):
        if 2 * i + 1 > self.size:
            return 2 * i
        else:
            if self.heaplist[2 * i] > self.heaplist[2 * i + 1]:
                return 2 * i
            else:
                return 2 * i + 1

作者：tian-di-jing-yi-BOwgvqig49
链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/nei-zhi-sort-kuai-pai-si-xiang-zui-da-dui-san-chon/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

堆 Heap

Idea​

P Implementation​

sample​

Codes​

Idea

P Implementation

sample

Codes