算法不想学(二): 堆排序和top k

原创

sean_yang

发布于 2020-07-18 15:52:31

4620

发布于 2020-07-18 15:52:31

文章被收录于专栏：Sorrower的专栏

算法不想学(一): 随缘匹配

前言

最近面试的时候, 遇到了让我手撕堆排序的情况, 不撕不知道, 一撕就头皮发麻, 所以复盘的时候, 决定理一下这个问题. 其实堆排序不考虑逻辑结构的情况下, 就是高级一点的选择排序, 核心就是条件交换, 所以理清这个条件, 问题就迎刃而解了. top k问题是一个常见的海量数据问题, 简单来说, 就是从内存一次存不下级别的数据里面找出最大/最小的k的元素, 可以有很多解法, 而最常见有效的, 就是堆排序. 例如网游里面的排行榜, 就是top k问题.

堆排序

一次排序

typedef bool(*fp)(int, int);

void makeHeapOnce(vector<int> &data, int start, int end, fp f) {
    int dad = start;
    int son = start * 2 + 1; // left

    while (son < end) {
        if ((son + 1) < end && bind(f, data[son + 1], data[son])())
            ++son;
        if (bind(f, data[dad], data[son])())
            return;
        
        swap(data[son], data[dad]);
        dad = son;
        son = 2 * dad + 1;
    }
}

首先说说下标问题, 如果你想要从父节点到左孩子, 2 * dad + 1即可, 如果你想从任一孩子到父节点, floor((son - 1) / 2)即可. 然后bind值得一提, 这里的f其实就是函数指针, 假如f对应的是小于判断函数, 那么就意味着构建小顶堆, 反之, 就是大顶堆. 为什么这里要装X用上bind呢? 主要是之前某次面试, 面试官让我实现一个可以捕获外部参数的匿名函数, 最后解决方案就是利用bind, 所以这里也顺带用上. 最后说说逻辑, 假设现在小顶堆, 当右孩子的值小于左孩子, 那么son就移至右孩子, 否则不变; 如果父节点已经小于小的那个孩子, 就可以返回, 否则交换, 当然这是建立在底下已经构建完成的情况下. 所以为了保证底下是构建完成的, 每次交换都需要将父节点换到交换的子节点, 然后继续深入进行构建.

构建堆

这样一来从start到end就完成了堆构建. 所以要把全部数据进行堆构建, 只需要把所有父节点跑一边这个函数即可.

void makeHeap(vector<int> &data, fp f) {
    if (data.empty()) {
        return;
    }

    // 建堆
    for (int i = static_cast<int>(data.size() / 2 - 1); i >= 0; --i) {
        makeHeapOnce(data, i, data.size(), f);
    }
}

那么哪些是父节点呢, 换句话说, 哪些是叶子节点呢? 由于堆实际是完全二叉树, 子节点个数就是size / 2 + 1, 父节点个数就是size / 2 - 1.

排序输出

之前也说了, 堆排序其实是高级选择排序, 那么如何能得到一个排好的序列呢?

void heap2arr(vector<int> &data, fp f) {
    // 选择排序
    for (int i = static_cast<int>(data.size() - 1); i > 0; --i) {
        swap(data[0], data[i]);
        makeHeapOnce(data, 0, i, f);
    }
}

逻辑就是把堆顶和最后一个未排序元素交换, 然后重新建堆. 也就是说, 每次交换都排序好了一个元素.

演示

都说没事走两步, 那我们就写个main试一下:

int main() {
    vector<int> data = {3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6};

    fp f = smaller;

    heapSort(data, f);
    printHeap(data);

    return 0;
}

这里选择了smaller, 也就是小顶堆, 那么输出就是倒序, 因为每次将最小的放置最后.

插入

或许应该考虑下插入的问题. 思路就是将新增元素放置到最后, 然后逐步比较它和父节点的大小, 直至到达根节点, 结束.

void heapInsert(vector<int> &heap, int insert, fp f) {
    if (heap.empty()) {
        heap.push_back(insert);
        return;
    }

    heap.push_back(insert);
    int parent = 0;
    int cur = static_cast<int>(heap.size() - 1);

    while (cur) {
        parent = (cur - 1) / 2;
        if (bind(f, heap[cur], heap[parent])()) {
            swap(heap[cur], heap[parent]);
        }
        cur = parent;
    }
}

top k

到这里, 堆的问题就说的差不多了, 比起快排归并, 你会发现它其实连递归都没有用到, 确实可以归为简单又有效的排序. 如果手撕都办不到, 别人挂你确实没毛病. 那么top k问题怎么利用堆呢? 建立一个k大小的小顶堆然后把剩余的数据和堆顶比较, 如果大于堆顶, 堆顶赋值为该元素, 并重新建整个k大小的堆; 否则, 跳过.

int main() {
    vector<int> data = {3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6};

    int k = 5;

    fp f = smaller;

    vector<int> topK(data.begin(), data.begin() + k);
    makeHeap(topK, f);

    auto it = data.begin() + k;
    for (; it != data.end(); ++it) {
        if (*it > topK[0]) {
            topK[0] = *it;
            makeHeap(topK, f);
        }
    }

    heap2arr(topK, f);
    printHeap(topK);

    return 0;
}