顺序读取数组中的前K个元素,构建小根堆。
小根堆的特点是根元素最小,并且一次调整(deleteMin)操作的时间复杂度为log(2,K)。
接下来从数组中取下一个元素,如果该元素不比堆顶元素大,则丢弃;否则用它替换堆顶元素,然后调整小根堆。
当把数组中的元素全部读出来后,小根堆中保留的就是前K大的元素。
初始建堆操作需要K * log(2, k)
–这是最多的操作次数,从数组中读取后N-K
个元素和堆顶元素一一比较,最坏的情况是每次都要替换堆顶元素,都要调整小根堆,复杂度为(N-K) * log(2,K)
。总的复杂度为O(N*log(2,K))
。
###找出最小的k个数呢?
和最大的k个数的思想是相同的,只是这里建立的是是大根堆