【STL源码剖析读书笔记】自己实现priority_queue之MyPriorityQueue

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

MyPriorityQueue.h

#ifndef MY_PRORITY_QUEUE_h
#define MY_PRORITY_QUEUE_h
#include "MyHeap.h"

template<typename T,typename Compare=MyLess<T>>
class MyPriorityQueue{
private:
	MyHeap<T, Compare> heap; //底层用堆实现
	const int top_index = 1;
public:
	MyPriorityQueue() :heap(){}

	template<typename InputIterator>
	MyPriorityQueue(InputIterator first, InputIterator last){
		heap.initial_heap(first, last);
		heap.make_heap();
	}

	bool empty(){ return heap.get_vector().size() == 1; } //注意heap的底层的vector第一个元素保留
	int size(){ return heap.get_vector().size() - 1; }
	T top(){ return heap.get_vector()[top_index]; }

	void push(const T& t){
		heap.push_heap(t);
	}
	void pop(){
		heap.pop_heap();
		heap.get_vector().erase(--heap.get_vector().end());
	}
};

#endif

main.cpp

#include "MyPriorityQueue.h"
using namespace std;

int main(){
	int ia[] = { 24, 26, 31, 13, 19, 21, 65, 68, 16 };
	MyPriorityQueue<int> que1(begin(ia), end(ia));
	cout << "top:" << que1.top() << endl; //top:68
	cout << "size:" << que1.size() << endl;//size:9

	que1.pop();
	cout << "top:" << que1.top() << endl;//top:65
	cout << "size:" << que1.size() << endl;//size:8

	que1.push(100);
	cout << "top:" << que1.top() << endl; //top:100
	cout << "size:" << que1.size() << endl;//size:9
	cout << endl;

	MyPriorityQueue<int,MyGreater<int>> que2(begin(ia), end(ia));
	cout << "top:" << que2.top() << endl; //top:13
	cout << "size:" << que2.size() << endl;//size:9

	que2.pop();
	cout << "top:" << que2.top() << endl;//top:16
	cout << "size:" << que2.size() << endl;//size:8

	que2.push(1);
	cout << "top:" << que2.top() << endl;//top:1
	cout << "size:" << que2.size() << endl;//size:9
	cout << endl;

	MyPriorityQueue<int> que3;
	cout << (que3.empty() ? "empty" : "not empty") << endl;//empty
	que3.push(3);
	que3.push(2);
	que3.push(4);
	que3.push(5);
	que3.push(1);
	cout << "top:" << que3.top() << endl; //top:5
	cout << "size:" << que3.size() << endl;//size:5

	que3.pop();
	cout << "top:" << que3.top() << endl;//top:4
	cout << "size:" << que3.size() << endl;//size:4

	system("pause");
	return 0;
}