#include <iostream>

#include <list>

using namespace std;

struct Node{

    int value;

    Node *next = NULL;

};


///堆排序（调整堆）

void HeapAdjust(Node* heap, int i, int length){

    int min = i;

    int lch = *i+;

    int rch = *i+;

    if(i <= (length-)/){

        if(lch < length && heap[min].value > heap[lch].value){

            min = lch;

        }

        if(rch < length && heap[min].value > heap[rch].value){

            min = rch;

        }

        if(min != i){

            swap(heap[min], heap[i]);

            HeapAdjust(heap, min, length);

        }

    }

}

///堆排序（建堆）

void BuildHeap(Node* heap, int length)

{
　　 ///要确定好是-2,还是-1

    for(int i = (length-)/; i >=; i--){

        HeapAdjust(heap, i, length);

    }

}


///主要排序函数

void listnodesort(list<list<Node> >* listlistnode)

{

    list<Node> listTotal;

    int length = (*listlistnode).size();

    Node* heap = new Node[length];

    int i = ;

    for(list<list<Node> >::iterator iter = (*listlistnode).begin(); iter !=(*listlistnode).end(); iter ++){

        heap[i] = (*iter).front();

        i++;

    }

    BuildHeap(heap, length);

    while(length>){

        listTotal.push_back(heap[]);

        if(length == ){

            break;

        }

        if(heap[].next == NULL){

            heap[] = heap[length-];

            length -=;

        }

        else{

            heap[] = *(heap[].next);

        }

        HeapAdjust(heap, , length);

    }

    cout << "totalList: ";

    for(list<Node>::iterator it=listTotal.begin(); it!=listTotal.end(); it++){

        cout << (*it).value << " ";

    }

    cout << endl;

}

list<list<Node> > buildListList(int sum, int interval)

{

    list<list<Node> > listlistnode;

    for(int i = ; i<interval; i++){

        list<Node> listnode;

        ///mode 1: start

        Node* node = new Node(); ///此处一定要用new分配一个内存，不能直接使用Node node;

        int j = i;

        while(j<sum){

            Node* nodeNext = new Node();

            node->value = j;

            if(j+interval > sum){

                node->next = NULL;

            }

            else

                node->next = nodeNext;

            listnode.push_back(*node);

            node = nodeNext;

            j+=interval;

        }

        ///mode 1: end

        ///mode2:start

//        int j = i;

//        Node* head = NULL;

//        Node* endp = NULL;

//        while(j<sum){

//            Node* node = new Node();

//            node->value = j;

//            node->next = NULL;

//            if(head == NULL){

//                head = node;

//                endp = node;

//            }

//            else{

//                endp->next = node;

//                endp = node;   ///此处也不可忘了

//            }

//            j=j+interval;

//        }

//        while(head != NULL){

//            listnode.push_back(*head);

//            head = head->next;

//        }

        /// mode 2:end

        listlistnode.push_back(listnode);

    }

    return listlistnode;

}

void print(list<list<Node> > *listlistnode) ///到底是传值还是传指针，后续代码块中的操作也要做相应变动；

{

    for(list<list<Node> >::iterator iter=(*listlistnode).begin(); iter != (*listlistnode).end(); iter++){

        list<Node> listnode = *iter;           ///迭代器解地址后就是其内部所指内容

        for(list<Node>::iterator it=listnode.begin(); it!=listnode.end(); it++){

            cout << (*it).value << " ";

        }

        cout << endl;

    }

}

int main()

{

    list<list<Node> > listlistnode = buildListList(,);

    print(&listlistnode);

    listnodesort(&listlistnode);  ///根据函数的定义决定是传值还是传指针

    cout << "Hello world!" << endl;

    return ;

}

　　 map<int, int> mapNode;

    for(list<list<Node> >::iterator iter=listlistnode.begin(); iter != listlistnode.end(); iter++){

        list<Node> listnode = *iter;

        for(list<Node>::iterator it=listnode.begin(); it!=listnode.end(); it++){
　　　　　　　　///如果不存在则插入，如果存在则key相应得value++即可。

            if(mapNode.count((*it).value)==)

                mapNode.insert(pair<int, int> ((*it).value,));

            else{

                mapNode[(*it).value]++;

            }

        }

    }

    for(map<int, int>::iterator it = mapNode.begin(); it!=mapNode.end(); it++){

        cout << it->first << " " << it->second << endl;

    }