【STL源码剖析读书笔记】自己实现Heap算法之MyHeap（底层容器用vector）

MyHeap.h

#ifndef MY_HEAP_H
#define MY_HEAP_H

#include<iostream>
#include<vector>

#define max_value -99999999
//仿函数
template<typename T>
struct MyLess{
bool operator()(const T& x, const T& y) const { return x < y; }
};
template<typename T>
struct MyGreater{
bool operator()(const T& x, const T& y) const { return x > y; }
};

template<typename T, typename Compare = MyLess<T>>
class MyHeap{
private:
std::vector<T> vec; //堆的底层容器
int num_of_element; //堆中元素个数
const int start_index=1; //堆在底层容器中从位置1开始
Compare comp;
public:
//用了一个小技巧，将vector的#0元素保留，可知某节点位于vector的i处时，其左子节点位于2*i处，右子节点位于2*i+1处，父节点位于i/2处
MyHeap() :num_of_element(0){ vec.push_back(max_value); } 
template<typename RandomAccessIterator>
void initial_heap(RandomAccessIterator begin, RandomAccessIterator end);
void push_heap(T element);
void pop_heap();
void sort_heap();
void make_heap();
void percolate_up(int hole_index, T value); //上溯程序
void adjust_heap(int hole_index, T value); //调整程序，包括下溯操作和上溯操作
void print_heap();
std::vector<T>& get_vector(){ return vec;}
};
//initial_heap(RandomAccessIterator begin, RandomAccessIterator end)
template<typename T, typename Compare>
template<typename RandomAccessIterator>
void MyHeap<T, Compare>::initial_heap(RandomAccessIterator begin, RandomAccessIterator end){
for (RandomAccessIterator it = begin; it != end; ++it){
vec.push_back(*it);
++num_of_element;
}
}
//push_heap(T element)
template<typename T, typename Compare>
void MyHeap<T, Compare>::push_heap(T element){
vec.push_back(element);
++num_of_element;
percolate_up(num_of_element, element);
}
//percolate_up(int hole_index, T value)
template<typename T, typename Compare>
void MyHeap<T, Compare>::percolate_up(int hole_index, T value){
int parent = hole_index / 2; //找出洞节点的父节点
while (hole_index > start_index&&comp(vec[parent],value)){//没到顶点且父值小于插入值
vec[hole_index] = vec[parent];//洞值为父值
hole_index = parent; //调整洞号
parent = hole_index / 2; //新洞的父节点
}
vec[hole_index] = value; //洞值为插入值
}
//pop_heap()
template<typename T, typename Compare>
void MyHeap<T, Compare>::pop_heap(){
T adjust_value = vec[num_of_element];//堆的最后一个节点需要调整
vec[num_of_element] = vec[start_index];//vec中最后一个元素为最大值
--num_of_element; //堆中元素减1
adjust_heap(start_index, adjust_value);
}
//adjust_heap(int hole_index, T value)
template<typename T, typename Compare>
void MyHeap<T, Compare>::adjust_heap(int hole_index, T value){
int right_child = 2 * hole_index + 1; //洞节点的右子节点
while (right_child <= num_of_element){
if (comp(vec[right_child],vec[right_child - 1])) //比较左右两个子节点的值
--right_child;
vec[hole_index] = vec[right_child];//洞值为左右两个子节点中较大的值
hole_index = right_child; //调整洞号
right_child = 2 * hole_index + 1; //新洞节点的右子节点
}
if (right_child == num_of_element + 1){ //没有右子节点，只有左子节点
vec[hole_index] = vec[right_child - 1]; //左子值为洞值
hole_index = right_child - 1;//洞节点为左子节点
}
vec[hole_index] = value; //洞值为插入值
//percolate_up(hole_index, value); //此时可能尚未满足次序特性，执行上溯操作,可能有问题
//注意，跟STL源码剖析说执行一次percolate up操作有区别，执行一次可能会出错
int yejiedian = num_of_element; 
while (yejiedian >= hole_index){
percolate_up(yejiedian, vec[yejiedian]); //此时可能尚未满足次序特性，执行上溯操作
--yejiedian;
}
}
//sort_heap()
template<typename T, typename Compare>
void MyHeap<T, Compare>::sort_heap(){
while (num_of_element > 0)
pop_heap();
}
//make_heap()
template<typename T, typename Compare>
void MyHeap<T, Compare>::make_heap(){
cout << "make heap过程：" << endl;
if (num_of_element < 2) //长度为0或1,不必重新排列
return;
int parent = num_of_element / 2; //第一个需要重排的子树头部
while (true){
adjust_heap(parent, vec[parent]);
print_heap();
if (parent == 1) //走完根节点就结束
return;
--parent;
}
}
//print_heap()
template<typename T, typename Compare>
void MyHeap<T, Compare>::print_heap(){
for (int i = 1; i <= num_of_element; ++i)
std::cout << vec[i] << " ";
std::cout << std::endl;
}
#endif

main.cpp

#include"MyHeap.h"
using namespace std;

int main(){
//int ia[] = { 24, 26, 31, 13, 19, 21, 65, 68, 16 };
int ia[] = { 24, 26, 31, 68, 19, 21, 13, 16, 65 };
MyHeap<int> heap;
cout << "大顶堆" << endl;
heap.initial_heap(begin(ia),end(ia));
cout << "initial heap:";
heap.print_heap();

heap.make_heap();
cout << "make heap:";
heap.print_heap();

heap.push_heap(50);
cout << "push heap:";
heap.print_heap();

heap.pop_heap();
heap.get_vector().pop_back();
cout << "pop heap:";
heap.print_heap();

heap.sort_heap();
cout << "sort heap:";
for (int i = 1; i <= 9; ++i)
cout << heap.get_vector()[i] << " ";
cout << endl;

MyHeap<int,MyGreater<int>> heap2;
cout << endl << "小顶堆" << endl;
heap2.initial_heap(begin(ia), end(ia));
cout << "initial heap:";
heap2.print_heap();

heap2.make_heap();
cout << "make heap:";
heap2.print_heap();

heap2.push_heap(50);
cout << "push heap:";
heap2.print_heap();

heap2.pop_heap();
heap2.get_vector().pop_back();
cout << "pop heap:";
heap2.print_heap();

heap2.sort_heap();
cout << "sort heap:";
for (int i = 1; i <= 9; ++i)
cout << heap2.get_vector()[i] << " ";
cout << endl;

system("pause");
return 0;
}