Top N（前N大或前N小）的算法问题

快速选择算法

下面是使用JavaScript实现快速选择算法来找到前N个最大的元素：

function partition(arr, left, right) {
    let pivot = arr[right];
    let i = left;
    for (let j = left; j < right; j++) {
        if (arr[j] >= pivot) {  // 注意这里是 >= ，因为我们要找的是前N个最大的元素
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++;
        }
    }
    [arr[i], arr[right]] = [arr[right], arr[i]];
    return i;
}

function quickselect(arr, left, right, k) {
    if (left <= right) {
        let pivotIndex = partition(arr, left, right);
        if (pivotIndex === k) {
            return arr.slice(0, k + 1);
        } else if (pivotIndex < k) {
            return quickselect(arr, pivotIndex + 1, right, k);
        } else {
            return quickselect(arr, left, pivotIndex - 1, k);
        }
    }
    return [];
}

function findTopNElements(arr, n) {
    if (n <= 0) {
        return [];
    }
    if (n >= arr.length) {
        return arr.slice().sort((a, b) => b - a);
    }
    return quickselect(arr, 0, arr.length - 1, n - 1);
}

// 示例用法
const arr = [3, 2, 1, 5, 6, 4];
const n = 3;
const topNElements = findTopNElements(arr, n);
console.log(`前${n}个最大的元素:`, topNElements);

解释：

1. partition函数：这个函数用于将数组分成两部分，以选择的枢轴为基准，将大于等于枢轴的元素放在左边，小于枢轴的元素放在右边。这里选择数组的最后一个元素作为枢轴。

2. quickselect函数：这是一个递归函数，用于在分区后选择第k个最大的元素。如果分区点正好是k，则返回前k个元素。如果分区点小于k，则递归处理右半部分，否则处理左半部分。

3. findTopNElements函数：这是主函数，用于处理特殊情况（如n小于等于0或n大于等于数组长度），并调用quickselect函数。

通过以上代码，可以高效地找到数组中前N个最大的元素。

优先队列

使用优先队列（最小堆）算法找到前N个最大的元素，可以使用JavaScript中的MinHeap来实现。我们将数组中的元素依次插入到一个大小为N的最小堆中，如果堆的大小超过N，就移除堆顶元素（最小的元素）。最终，堆中存放的就是前N个最大的元素。

下面是实现代码：

class MinHeap {
    constructor() {
        this.heap = [];
    }

    insert(value) {
        this.heap.push(value);
        this.bubbleUp();
    }

    bubbleUp() {
        let index = this.heap.length - 1;
        while (index > 0) {
            let parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[parentIndex] <= this.heap[index]) break;
            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
            index = parentIndex;
        }
    }

    extractMin() {
        if (this.heap.length === 1) return this.heap.pop();
        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.sinkDown(0);
        return min;
    }

    sinkDown(index) {
        const length = this.heap.length;
        const element = this.heap[index];
        while (true) {
            let leftChildIndex = 2 * index + 1;
            let rightChildIndex = 2 * index + 2;
            let leftChild, rightChild;
            let swap = null;

            if (leftChildIndex < length) {
                leftChild = this.heap[leftChildIndex];
                if (leftChild < element) swap = leftChildIndex;
            }

            if (rightChildIndex < length) {
                rightChild = this.heap[rightChildIndex];
                if ((swap === null && rightChild < element) || (swap !== null && rightChild < leftChild)) {
                    swap = rightChildIndex;
                }
            }

            if (swap === null) break;
            [this.heap[index], this.heap[swap]] = [this.heap[swap], this.heap[index]];
            index = swap;
        }
    }

    size() {
        return this.heap.length;
    }

    peek() {
        return this.heap[0];
    }
}

function findTopNElements(arr, n) {
    if (n <= 0) {
        return [];
    }
    if (n >= arr.length) {
        return arr.slice().sort((a, b) => b - a);
    }

    const minHeap = new MinHeap();
    for (let i = 0; i < arr.length; i++) {
        minHeap.insert(arr[i]);
        if (minHeap.size() > n) {
            minHeap.extractMin();
        }
    }

    const result = [];
    while (minHeap.size() > 0) {
        result.push(minHeap.extractMin());
    }
    return result.sort((a, b) => b - a);  // 最后结果需要从大到小排序
}

// 示例用法
const arr = [3, 2, 1, 5, 6, 4];
const n = 3;
const topNElements = findTopNElements(arr, n);
console.log(`前${n}个最大的元素:`, topNElements);

解释：

1. MinHeap类：实现了一个最小堆，包括插入元素、移除最小元素、获取堆的大小、查看堆顶元素等操作。

2. findTopNElements函数：这个函数使用最小堆来存储前N个最大的元素。如果堆的大小超过N，就移除堆顶元素。最终，堆中存放的就是前N个最大的元素。

3. 示例用法：创建一个数组和N值，并调用findTopNElements函数来找到前N个最大的元素。最后输出结果。

通过这个代码，你可以高效地找到数组中前N个最大的元素。