c++ 堆操作算法

奥海

主要函数

• make_heap():从序列构造堆。
  
• pop_heap():从堆中弹出元素。
  
• push_heap():向堆中加入元素。
  
• sort_heap():给堆排序。
  
• is_heap():判断序列是否是一个有效的堆
  
• is_heap_until():判断序列是否是一个有效的堆，返回一个迭代器
  

make_heap()函数模板原型为:

template<class RandomAccessIterator>
void make_heap (RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void make_heap(RandomAccessiterator first, RandomAccessIterator last, Compare comp) ;make_heap()函数将[first,last)区间构造成一个堆。第一个版本使用<来确定顺序，而第二个版本使用comp比较对象。
例子:
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
int main(){
    int a[] = {1, 4, 2, 10, 6, 5, 9, 7, 8, 3};
    cout<< "原始a[]: ";
    copy(a, a + 10, ostream_iterator<int>(cout, " "));
    cout<< endl;
    vector<int>v1(a, a + 10);
    make_heap(v1.begin(), v1.end(), greater<int>());
    cout<< "最小堆: ";
    copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
    cout<< endl;
    vector<int>v2(a, a + 10);
    make_heap(v2.begin(), v2.end(), less<int>());
    cout<< "最大堆: ";
    copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
    return 0;
}

建最小堆用的二元函数是greater,不是 less;建最大堆用的二元函数是less,而不是greater。与常规用到的二元函数语义正好相反。
pop_heap()函数模板原型为:

template<class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void pop_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp) ;pop_heap()函数假设[first, last)区间是一个有效堆，并将位置last -1处的值与first处的值进行交换使[first, last - 1]区间成为一个有效堆。第一个版本使用<来确定顺序，而第二个版本使用comp比较对象
例子:
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
int main(){
    int a[] = {1, 4, 2, 10, 6, 5, 9, 7, 8, 3};
    cout<< "原始a[]: ";
    copy(a, a + 10, ostream_iterator<int>(cout, " "));
    cout<< endl;
    vector<int>v1(a, a + 10);
    make_heap(v1.begin(), v1.end(), greater<int>());
    cout<< "最小堆: ";
    copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
    cout<< endl;
    vector<int>v2(a, a + 10);
    make_heap(v2.begin(), v2.end(), less<int>());
    cout<< "最大堆: ";
    copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
    cout<< endl;
   
    pop_heap(v2.begin(), v2.end());
    cout<< "堆中最大值： " ;
    cout<< *(v2.end() - 1) << endl;
    pop_heap(v2.begin(), v2.end() - 1);
    cout<< "堆中次大值： " ;
    cout<< *(v2.end() - 2) << endl;
    copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
    return 0;
}

可以看到，vector中存在脏数据，所以在使用pop_heap时要考虑数据的有效长度
push_heap()函数模板原型为:

template<class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);push_heap()函数假设[first, last - 1)区间是一个有效的堆，并将last - 1位置(即被假设为有效堆的区间后面的一个位置)上的值添加到堆中，使[first,last)区间成为一个有效堆。第一个版本使用<来确定顺序，而第二个版本使用comp比较对象。
sort_heap()函数模板原型为:

template<class RandomAccessIterator>
void sort_heap (RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp) ;sort_heap()函数假设[first,last)区间是一个有效堆，并对其进行排序。第一个版本使用<来确定顺序，而第二个版本使用comp比较对象。
is_heap()函数模板原型为:

template<class RandomAccessIterator>
bool is_heap(RandomAccessiterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp) ;如果区间[first, last]是一个有效的堆，函数 is_heap()将返回true，否则返回false。第一个版本使用<来确定顺序，而第二个版本使用comp比较对象。
is_heap_until()函数模板原型为:

template<class RandomAccessIterator>
RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last) ;
template<class RandomAccessIterator, class Compare>
RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last, Compare comp) ;如果区间[first, last)包含的元素少于两个，则返回last;否则返回迭代器it，而区间[first, it)是一个有效的堆。第一个版本使用<来确定顺序，而第二个版本使用comp 比较对象。
例子:
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
template<class T, class Pred = less<T>>
class MyHeap{
    Pred pr;
    vector<T> v;
    int ValSize;
public:
    MyHeap(T t[], int nSize):v(t, t + nSize){
        ValSize = nSize;
        if(!is_heap(v.begin(), v.begin() + ValSize)){
            make_heap(v.begin(), v.begin() + ValSize, pr);
        }
    }
    bool Insert(const T& t){
        v.push_back(t);
        ValSize++;
        push_heap(v.begin(), v.begin() + ValSize, pr);
        return true;
    }
    bool Remove(T& result){
        if(ValSize == 0)    return false;
        pop_heap(v.begin(), v.begin() + ValSize, pr);
        result = *(v.begin() + ValSize -1);
        ValSize--;
        return true;
    }
    bool Sort(){
         if(is_heap(v.begin(), v.begin() + ValSize)){
             sort_heap(v.begin(), v.begin() + ValSize);
             return true;
         }
         return false;
    }
    bool IsEmpty(){
        return ValSize == 0;
    }
    void Display(){
        copy(v.begin(), v.begin() + ValSize, ostream_iterator<int>(cout, " "));
    }
};
int main(){
    int a[] = {1, 4, 2, 10, 6, 5, 9, 7, 8, 3};
    MyHeap<int, greater<int>>m(a, 10);
    cout<< "原始堆: ";
    m.Display();
    cout<< endl;
    m.Insert(0);
    cout<< "插入0后为: ";
    m.Display();
    cout<< endl;
    int result;
    m.Remove(result);
    cout<< "堆中最小值为: " << result << endl;
    return 0;
}