开学算法之heap

[maiff]

开学之heap

---

最开始认识到堆是从知乎看来的，当时是看到一个题目：

有一个数量很大的乱序的数的集合，找出其中的top100

当时排名最高的答案是维护一个长度为100的min堆然后扫一遍就可以当时给的时间复杂度是O(NlogN)就觉得很是神奇。

堆

堆真的很神奇，这里只说是二叉堆，因为二叉堆的性质，完全可以用数组来表示。
一般可能在0上放一个head，这样二叉堆的左儿子就是2i，右儿子就是（2i+1）

插入

def insert(self,element):
    i = self.getSize() + 1
    self.elements.append(None)
    while self.elements[i/2] > element:
        self.elements[i] = self.elements[i/2]
        i/=2
        self.elements[i] = element

其中涉及到一个percolate up过程，就是先插入一个空的，插入的值跟父节点比较，一直往上一直大于父节点就停止。

删除最小

删除最小涉及到一个percolate down的过程。代码如下：

def siftdown(self,i):
    elements = self.elements
    tmp=elements[i]
    while(2*i<len(elements)):
        child=2*i
        if child+1 < len(elements):
            if(elements[child+1]<elements[child]):
                child+=1
        if(tmp>elements[child]):
            elements[i]=elements[child]
        else:
            break
        i=child
    elements[i]=tmp
    
def deleteMin(self):
    if self.isEmpty():
        raise Exception('heap is empty')
    temp = self.elements[1]
    self.elements[1]=self.elements[-1]
    self.elements.pop()
    self.siftdown(1)
    return temp

说一下这里的思路，这里这个下滤比上滤难理解一点。我这里借鉴了这里的思路，但是实现思路还是书（《数据结构与算法分析》下同）上的。
首先传进来的i就是要下滤的元素，找到他的子节点，左右比一下看谁更大或者更小，然后再跟父节点比较看是否需要交换，然后一直往下沉。这里需要强调两点：

1. 书上的思路跟那个链接的思路不一样，书上用了最小的交换次数，而链接每次都要交换，这里就有一个思路，我给他取个名吧————惰性交换
2. 为什么算法我没有用c去实现了，因为我觉得我的思路是对的但是总是编译不通过，没办法我就用python实现了，c跟脚本语言有什么差别了？就是堆是用数组实现的，c你需要手动维护一个长度，同时数组的长度在一开始就要规定，而在一般的脚本语言你大可不必这样做。这也是c快的原因吧。

BuildHeap

给你一堆数你怎么把他变成堆呢？

1. 当然你可以遍历然后一个一个插进去这里时间复杂度O（NlogN）
2. 这里书上给了一个算法：

for(i=n/2; i>0; i--)
    PercolateDown(i)

就是从最后一个叶子节点的父节点不停的下滤就得到一个heap，时间复杂度O（N）

应用

我最开始说了一个问题完全可以还有另外一种方式，把所有的数构造成heap然后不停的deleteMax就可以了。

堆排序

堆排序的思路很简单，我上面说的思路就是堆排序的思路当然有些优化方式，具体请看下一节算法篇————排序

总结

堆其实还有另外一个名字————优先队列，在操作系统里进程的调度也是通过堆实现的，具体怎么实现，我也不知道，不过我最近正在看linux内核