我们了解了树形结构之后,知道了二叉树,但是二叉树的具体用途我们还是不知道,今天就来看看一种特殊的二叉树–堆,它是一种完全二叉树,著名的topK问题就是用堆来求取的。可以求出一组数中的最大或者最小的元素。所使用的堆就是大根堆、小根堆,所谓大根堆就是根结点的值大于左右子树节点的值,反之就是小根堆了。先建个堆给大家看看,这里以建大堆为例,建堆呢,它有两个方法,向下调整和向上调整。 输入一个数组进行测试: 从结果可以看出我们的建堆操作成功,下面来看向上调整:
同样输入数组进行测试: 看完建堆之后,我们来看看用堆实现的优先级队列:
测试结果如下: 来看看topK问题:给出100(N)亿个数字,要求出前1000(M)大的数字,有两种解决方案: 方法一:用一个数组保存这些数字,直接在这个数组上建大堆,循环1000次取堆顶元素+调整操作,就能得到前1000大的元素,时间复杂度为o(N)+o(MlogN)。 方法二:先取集合中的前1000个元素放到一个数组中,建立一个小堆(堆顶元素就是前1000大元素的守门员)。再一个一个遍历集合中的数字,依次和守门员进行比较,如果这个元素比守门员大,就把守门员删掉(调整堆),再把当前元素入堆(调整堆),当把所有元素都遍历完之后,堆中的元素就是前1000大元素,时间复杂度为o(M)+o(NlogM)。 在topK问题中N远远大于M,把M看做1的话,得出二者时间复杂度差不多,但是使用方法1,内存可能不足,所以普遍使用方法2,它的运行效率也更高。举个简单的例子 关于堆的问题,就讲到这。大家如果想看堆排序,我在算法中的七大排序中有说明哦。