sgi 之heap, priority_queue

heap只能算是算法，而priority_queue只是封装了vector，所以又称为配接器。

由于在下面的实现中需要获得iterator所指向的类型，所以又用到了stl中的类型萃取技术

cconstruct.h

#ifndef C_CONSTRUCT_H #define C_CONSTRUCT_H #include <iostream> #include <new.h>inline void destroy(char *, char *){} inline void destroy(int *, int *){} inline void destroy(long *, long *){} inline void destroy(float *, float *){} inline void destroy(double *, double *){}//对于int* p，也可以调用这个函数，比较怪异 template <class T> inline void destroy(T* pointer) {pointer->~T(); }template <class ForwardIterator> inline void destroy(ForwardIterator first, ForwardIterator last) {for (; first < last ; ++first)destroy(first); }template <class T1, class T2> inline void construct(T1* p, const T2& value) {new (p) T1(value); }template <class _Iter> inline typename std::iterator_traits<_Iter>::value_type* __value_type(const _Iter&) {return static_cast<typename std::iterator_traits<_Iter>::value_type*>(0); }#endif

cheap.h

#ifndef C_HEAP_H #define C_HEAP_H #include "cconstruct.h" #include <iostream>//上溯。假设要上溯的值放在堆尾 template <class RandomAccessIterator, class Compare> void cpush_heap(RandomAccessIterator first, RandomAccessIterator last, Compare cmp ) {__cpush_heap(first, last, __value_type(first), cmp); }template <class RandomAccessIterator, class T, class Compare> void __cpush_heap(RandomAccessIterator first, RandomAccessIterator last, T*, Compare cmp) {size_t holeIndex = last - first - 1;size_t parent = (holeIndex - 1)/2;T value = *(last - 1);while (holeIndex > 0 && cmp(*(first + parent), value)) {*(first + holeIndex) = *(first + parent);holeIndex = parent;parent = (holeIndex - 1)/2;}*(first + holeIndex) = value; }//上溯操作只适用于在尾部添加元素，维持堆特性的操作template <class RandomAccessIterator, class Compare> void cpop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare cmp) {__cpop_heap(first, last, __value_type(first), cmp); }template <class RandomAccessIterator, class T, class Compare> void __cpop_heap(RandomAccessIterator first, RandomAccessIterator last, T*, Compare cmp) {T value = *(last - 1);*(last - 1) = *first;__cadjust_heap(first, 0, last - first - 1, value, cmp);//注意，此时的长度就不应该算上堆尾 }//向下走。value本来放在holeIndex template <class RandomAccessIterator, class T, class Compare> void __cadjust_heap(RandomAccessIterator first, size_t holeIndex, size_t len, T value, Compare cmp) {size_t firstChild = 2* holeIndex + 1;for ( ; firstChild < len; firstChild = 2* firstChild + 1) {if (firstChild + 1 < len && cmp(*(first + firstChild ), *(first + firstChild + 1)))++firstChild;if (!cmp(value, *(first + firstChild) ))//value >= childbreak;*(first + holeIndex) = *(first + firstChild);holeIndex = firstChild;}*(first + holeIndex) = value; }//输入必须是已经成堆的 template <class RandomAccessIterator, class Compare> void csort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare cmp) {while (last - first > 1) cpop_heap(first, last--, cmp); }template <class RandomAccessIterator, class Compare> void cmake_heap(RandomAccessIterator first, RandomAccessIterator last, Compare cmp) {__cmake_heap(first, last, __value_type(first), cmp); }template <class RandomAccessIterator, class T,class Compare> void __cmake_heap(RandomAccessIterator first, RandomAccessIterator last, T*, Compare cmp) {if (last - first < 2) return;size_t len = last - first;size_t holeIndex = (len - 2)/2;//从底向上，第一棵子树的头while (true) {__cadjust_heap(first, holeIndex, len, *(first + holeIndex), cmp);if (holeIndex == 0) return;--holeIndex;}}#endif
cqueue.h

#ifndef C_QUEUE_H #define C_QUEUE_H #include "cvector.h" #include "cheap.h" #include <iostream>template <class T, class Seq = cvector<T>, class Compare = less<typename Seq::value_type> > class cpriority_queue { public:typedef typename Seq::value_type value_type;typedef typename Seq::reference reference;typedef typename Seq::const_reference const_reference; protected:Seq c;//底层容器Compare comp;public:cpriority_queue() : c() {}template <class InputIterator>cpriority_queue(InputIterator first, InputIterator last, const Compare& x): c(first, last), comp(x) { cmake_heap(c.begin(), c.end(), comp); }template <class InputIterator>cpriority_queue(InputIterator first, InputIterator last): c(first, last){ cmake_heap(c.begin(), c.end(), comp); }/*void show() {Seq::iterator first = c.begin();for (;first != c.end(); ++first)std::cout<<*first<<" ";std::cout<<endl;}*/bool empty() const { return c.empty(); }size_t size() const { return c.size(); }const_reference top() const { return c.front(); }void push(const value_type& x) {c.push_back(x);cpush_heap(c.begin(), c.end(), comp);}void pop() {cpop_heap(c.begin(), c.end(), comp);c.pop_back();}};#endif

总结

以上是生活随笔为你收集整理的sgi 之heap, priority_queue的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。