classHeap{ constructor(list, compare = (a, b) => a - b) { this.left = index =>2 * index + 1 this.right = index =>2 * index + 2 this.parent = index =>Math.floor((index - 1) / 2) this.heapify = (index = 0) => { const { list } = this const leftIndex = this.left(index) const rightIndex = this.right(index) let maxIndex = index if (list[leftIndex] !== undefined && this.compare(list[maxIndex], list[leftIndex]) > 0) { maxIndex = leftIndex } if (list[rightIndex] !== undefined && this.compare(list[maxIndex], list[rightIndex]) > 0) { maxIndex = rightIndex } if (index !== maxIndex) { const temp = list[index] list[index] = list[maxIndex] list[maxIndex] = temp this.heapify(maxIndex) } } this.buildHeap = () => { for (let i = Math.floor(this.list.length / 2); i >= 0; i--) { this.heapify(i) } returnthis.list } this.extract = () => { const temp = this.list[0] this.list[0] = this.list[this.list.length - 1] this.list[this.list.length - 1] = temp const result = this.list.pop() this.heapify(0) return result } this.top = () => { returnthis.list[0] } this.insert = (item) => { const { list } = this list.push(item) let index = list.length - 1 let parentIndex = this.parent(index) while (list[parentIndex] !== undefined && this.compare(list[parentIndex], list[index]) > 0) { const temp = list[index] list[index] = list[parentIndex] list[parentIndex] = temp index = parentIndex parentIndex = this.parent(index) } } this.list = list this.compare = compare this.buildHeap() } }
var kClosest = function(points, k) { // 要找到最近的点,应该用最大堆存储 k 个最小的 var compare = function (a,b) { var A = a[0] * a[0] + a[1] * a[1] var B = b[1] * b[1] + b[0] * b[0] return B - A } var heap = new Heap([],(a,b) => { return compare(a,b) }) for(let i = 0 ; i < points.length ; i ++) { if (i < k) { heap.insert(points[i]) } else { var top = heap.top() // top 比 当前值大, 出top if(compare(points[i],top) > 0) { heap.extract() heap.insert(points[i]) } } } return heap.list };