[面试题]打印链表中前k大的数

题目

之前在刷leetcode的时候碰到过类似的题目，但是要求解第k大的数，那么只需要使用快慢指针，快指针先走k步，然后等快指针到达末尾时，慢指针指向的元素即为倒数第k的元素。

现在这个题目略有不同，是要求求链表中前k个元素，显然是大数据面试中的topk问题，可以建立一个最小堆来解决这个问题，每次遍历便将与堆顶元素比较，当大于堆顶元素时便插入堆，最后输出所有堆中元素即可。

代码

#include <iostream>
#include <vector>
using namespace std;

struct Node
{
    /* data */
    int val;
    Node *next;
    Node(int x){next=nullptr;val=x;}
};


template<class T>
class Heap
{
private:
    /* data */
    vector<T>vt;
public:
    Heap(){}
    Heap(const T *data, int k) 
    {
        createHeap(data, k);
    }
    void createHeap(const T *a, int k)
    {
        for (int i=0;i<k;i++){
            vt.push_back(a[i]);            
        }

        for (int i=(k-2)/2; i>=0; --i){
            adjustHeap(i);
        }
    }
    void adjustHeap(int pa)
    {
        int ch = pa * 2 + 1;
        while (ch < vt.size()){
            if (ch + 1 < vt.size() && vt[ch] > vt[ch+1]) ++ch;
            if (vt[ch] < vt[pa]){
                swap(vt[ch], vt[pa]);
                pa = ch;
                ch = pa * 2 + 1;
            }else {
                break;
            }
        }
    }

    T& top()
    {
        return vt[0];
    }

    void push(int& x)
    {
        vt.push_back(x);
        adjustHeap(vt.size()-1);
    }

    void print()
    {
        for (int i=0;i<vt.size();i++){
            cout<<vt[i]<<" ";
        }
        cout<<endl;
    }
    ~Heap() {}
};

void getTopK(int *a, int k, int len)
{
    Heap<int>hp(a, k);
    for (int i=k;i<len;i++){
        if (hp.top() < a[i]){
            hp.top() = a[i];
            hp.adjustHeap(0);
        }
    }
    hp.print();
}

void getListTopK(Node *head, int k, int len)
{
    int cnt = 0;
    Heap<int>hp;
    for (Node* p = head; p ; p=p->next)
    {
        if (cnt < k){
            hp.push(p->val);
            ++cnt;
        }else if (hp.top() < p->val){
            hp.top() = p->val;
            hp.adjustHeap(0);
        }
    }
    hp.print();
}

void test()
{
    int a[] = {1, 8, 7, 5, 6, 3, 4};
    int len = sizeof(a) / sizeof(a[0]);
    int k = 3;
    getTopK(a, k, len);
}

void testList()
{
    Node *vhead = new Node(-1);
    Node *ret = vhead;

    int a[] = {1, 8, 7, 5, 6, 3, 4};
    int len = 7;
    int k = 3;
    for (int i=0;i<len;i++){
        Node *p = new Node(a[i]);
        p->next = vhead->next;
        vhead->next = p;

        //vhead->next = p;
        //vhead = p;
    }

    getListTopK(ret->next, k, len);
}

int main()
{
    test();
    testList();
}