Catalog

• What is a heap?
  • Big root pile
  • Heap
  • Heap operation
• STL queue

What is a heap?

Heap is a data structure that can be used to implement priority queues

Big root pile

Big root heap, as the name implies, is the largest root node. First, we use the process of building small root heap to learn the idea of heap.

Heap

The following figure shows the process of small root piling

Heap operation

• Go up
• Sink
• insert
• Eject
• Crest

• Heap sort

  STL heap

  include in Library

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    vector<int> a;
    int num,n=10;
    for(int i=0;i<n;i++)
    {
        num = rand()%(233*2);
        a.push_back(num);
    }
    
    for(vector<int>::iterator i=a.begin();i!=a.end();i++) 
    {
        cout<<*i<<ends;
    }cout<<endl<<endl;

    make_heap(a.begin(),a.end());//Default big root heap
    for(vector<int>::iterator i=a.begin();i!=a.end();i++) 
    {
        cout<<*i<<ends;
    }cout<<endl<<endl;

    make_heap(a.begin(),a.end(),cmp);//Homemade little root pile
    for(vector<int>::iterator i=a.begin();i!=a.end();i++) 
    {
        cout<<*i<<ends;
    }cout<<endl<<endl;

    a.push_back(2333);
    push_heap(a.begin(),a.end(),cmp);//Add new elements to the heap
    for(vector<int>::iterator i=a.begin();i!=a.end();i++) 
    {
        cout<<*i<<ends;
    }cout<<endl<<endl;
    
    a.pop_back(); //Delete tail
    for(vector<int>::iterator i=a.begin();i!=a.end();i++) 
    {
        cout<<*i<<ends;
    }cout<<endl<<endl;

    getchar();getchar();getchar();getchar();
    return 0;
}

STL queue

include in Library

#include<bits/stdc++.h>
using namespace std;

struct student{
    int grade;
    string name;
};
struct cmp{
    bool operator() (student s1,student s2){
    return s1.grade < s2.grade;
    }
};

int main(int argc, char const *argv[])
{
    int n=10,num;
    /*
    1. push [Join the team and get to the end of the team]
    2. pop [Team leader element out of the team]
    3. size [Return the number of elements in the queue]
    4. front [Return the first element in the queue]
    5. back [Return the last element in the queue]
    6. empty [Judge whether the queue is empty]
    */
    //Cout < < queue: < endl;
    queue<int> a;
    for(int i=1;i<n;i++){
        num = rand()%233;
        a.push(num);
    }
    //Sequence length
    cout<<a.size()<<endl;
    //Sequence header element
    cout<<a.front()<<endl;
    //Sequence tail element
    cout<<a.back()<<endl;
    //Whether the sequence is empty
    while(!a.empty()){
        cout<<a.front()<<ends;
        a.pop();
    }cout<<endl<<endl;
    
    priority_queue<int> pq_1;
    for(int i=1;i<n;i++){
        num = rand()%233;
        pq_1.push(num);
    }
    //By default, the highest value is at the head of the team (descending)
    while(!pq_1.empty()){
        //Note that the access header element here is. top
        cout<<pq_1.top()<<ends;
        pq_1.pop();
    }cout<<endl;
    
    //In the following cases, the smaller one is at the head of the team (ascending)
    priority_queue<int,vector<int>,greater<int> > pq_2;
    for(int i=1;i<n;i++){
        num = rand()%233;
        pq_2.push(num);
    }

    while(!pq_2.empty()){
        //Note that the access header element here is. top
        cout<<pq_2.top()<<ends;
        pq_2.pop();
    }cout<<endl;cout<<endl;
    
    //Operator overloading 
    
    priority_queue<student,vector<student>,cmp> q;
    student s1,s2,s3;
    s1.grade = 90;
    s1.name = "Tom";

    s2.grade = 80;
    s2.name = "Jerry";

    s3.grade = 100;
    s3.name = "Kevin";

    q.push(s1);
    q.push(s2);
    q.push(s3);

    while(!q.empty()){
        cout<<q.top().name<<":"<<q.top().grade<<endl;
        q.pop();
    } 
    getchar();
    return 0;
}