PHP 最小堆实现第K大元素 class MinHeap extends SplHeap { //用最小堆存储第K大元素 public function compare( $value1, $value2 ) { return ( $value2 - $value1 ); } } class KthLargest { public $k; public $heap; /** * @param Integer $k * @param Integer[] $nums */ function __construct($k, $nums) { $this->k = $k; $this->heap = new MinHeap(); foreach($nums as $num) { $this->add($num); } } /** * @param Integer $val * @return Integer */ function add($val) { if($this->heap->count()<$this->k){ $this->heap->insert($val); }else{ if($val>$this->heap->top()){ $this->heap->insert($val); $this->heap->extract(); } } return $this->heap->top(); } }

这个题面试真遇到过,当时回答的也是 维护一个 k 长度的数组,每次加入都进行排序,先跟最小的比,如果比最小的都小就直接抛弃.比最小的大就挨个与数组中元素比较. 时间复杂度是 n*k

上面那个Go语言的有问题，他不能保证一直都是满足小顶堆的限制的，因为push的时候调用的是自己的方法而不是堆的方法，所以不会检测。下面是我写的 type IntHead []int func (i IntHead) Len() int { return len(i)} func (In IntHead) Less(i ,j int) bool { return In[i] < In[j]} func (In IntHead) Swap(i, j int) { In[i], In[j] = In[j], In[i] } func (In *IntHead) Push(x interface{}) { *In = append(*In, x.(int)) } func (In *IntHead) Pop() interface{} { old := *In n := len(old) x := old[n -1] *In = old[0:n-1] return x } type KthLargest struct { K int H *IntHead } func Constructor(k int, nums []int) KthLargest { min := &IntHead{} heap.Init(min) kth := KthLargest{K:k, H:min} for _, num := range nums { kth.Add(num) } return kth } func (this *KthLargest) Add(val int) int { if this.H.Len() == 1 && (*this.H)[0] == 0 && val == -1 { min := &IntHead{-1,0} heap.Init(min) this.H = min } if this.H.Len() < this.K { heap.Push(this.H, val) } else if (*this.H)[0] < val { heap.Pop(this.H) heap.Push(this.H, val) } return (*this.H)[0] } }

今天看到一个算法测试题，讲到了优先级队列，大顶堆和小顶堆，而且我还通过课程的理解讲给了同事，竟然给他讲明白了，很有成就感

老师，学习课程时，是不是不推荐使用不支持heap的语言，比如c？否则精力花在自己实现heap上，没有必要。

GO语言版本实现： package main import ( "container/heap" "fmt" ) type IntHeap []int func (h IntHeap) Len() int { return len(h) } func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) } func (h *IntHeap) Pop() interface{} { old := *h n := len(old) x := old[n-1] *h = old[0 : n-1] return x } // return the minimum func (h *IntHeap) Peek() interface{} { return (*h)[0] } type KthLargest struct { minHeap *IntHeap k int } func Constructor(k int, nums []int) KthLargest { h := &IntHeap{} heap.Init(h) kth := KthLargest{minHeap: h, k: k} for _, v := range nums { kth.Add(v) } return kth } func (this *KthLargest) Add(val int) int { if this.minHeap.Len() < this.k { this.minHeap.Push(val) } else if this.minHeap.Peek().(int) < val { heap.Remove(this.minHeap, 0) this.minHeap.Push(val) } return this.minHeap.Peek().(int) } /** * Your KthLargest object will be instantiated and called as such: * obj := Constructor(k, nums); * param_1 := obj.Add(val); */ func main() { k := 3 nums := []int{4, 5, 8, 2} obj := Constructor(k, nums) fmt.Println(obj.Add(3)) fmt.Println(obj.Add(5)) fmt.Println(obj.Add(10)) fmt.Println(obj.Add(9)) fmt.Println(obj.Add(4)) }

老师 假如使用优先队列的方式来实现 那么如何计算实际复杂度呢 不用考虑优先队列的实现的 时间复杂对吗

老师 ，请问一下用python实现的话有内建的miniheap吗？

miniheap是个什么概念 和代码里面的优先队列啥关系 感觉不是很清楚 内部是如何保证最小元素在最上面

作者好,如果问题的发起者说不能用 java 现成的 PriortyQueue 的话是不是还需要单独实现这个排序的算法呢?