fork(1) download
copy 
  1. #include <iostream>
  2. #include <cstdlib>
  3.  
  4. //функтор по-умолчанию от наибольшего к меньшему
  5. template<typename T>
  6. struct pcmp {
  7. 	bool operator () (const T& a, const T& b)const{
  8. 		return (a > b);
  9. 	}
  10. };
  11.  
  12. //приоритетная очредь на базе бинарной кучи
  13. template<typename T, typename Cmp = pcmp<T> >
  14. class pqueue {
  15. private:
  16. 	T*     arr;
  17. 	size_t cnt;
  18. 	size_t mem;
  19. 	Cmp    cmp;
  20. public:
  21. 	pqueue(void):arr(NULL),
  22. 	             cnt(0),
  23. 				 mem(16){}
  24. 	pqueue(const T* f, const T* l):arr(NULL),
  25. 	                               cnt(0),
  26. 	                               mem(16){
  27. 		this->copy(f, l);
  28. 	}
  29. 	~pqueue(){
  30. 		this->clear();
  31. 	}
  32. 	pqueue(const pqueue&);
  33. 	pqueue& operator = (const pqueue&);
  34. public:
  35.  
  36. 	//добавление
  37. 	bool push(const T& val){	
  38. 		if(! this->_alloc_array(1))
  39. 			return false;
  40.  
  41. 		arr[cnt++] = val;
  42. 		size_t   i = cnt - 1;
  43. 		size_t   p = (i - 1) >> 1;
  44. 		while((i > 0) && cmp(val, arr[p])){
  45. 			std::swap(arr[p], arr[i]);
  46. 			i = p;
  47. 			p = (p - 1) >> 1;
  48. 		}
  49. 		return true;
  50. 	}
  51.  
  52. 	//удаление
  53. 	void pop(void){
  54. 		if(cnt > 0){
  55. 			arr[0] = arr[--cnt];
  56. 			this->heapify(0);
  57. 		}
  58. 		if(! cnt)
  59. 			this->clear();
  60. 	}
  61.  
  62. 	//копирование массива
  63. 	bool copy(const T* f, const T* l){
  64. 		size_t num = (size_t)(l - f);
  65. 		cnt = 0;
  66. 		if(! this->_alloc_array(num))
  67. 			return false;
  68.  
  69. 		T* p = arr;
  70. 		while(f != l)
  71. 			*p++ = *f++;
  72. 		cnt = num;
  73.  
  74. 		for(size_t i = cnt >> 1; i > 0; --i) 
  75. 			this->heapify(i);
  76. 		this->heapify(0);
  77. 		return true;
  78. 	}
  79.  
  80. 	//удаление всех
  81. 	void clear(void){
  82. 		if(arr != NULL)
  83. 			delete[] arr;
  84. 		arr = NULL;
  85. 		cnt = 0;
  86. 		mem = 16;
  87. 	}
  88.  
  89. 	T& top(void) { return arr[0]; }
  90. 	T& top(void) const { return arr[0]; }
  91.  
  92. 	size_t size(void) const {
  93. 		return cnt;
  94. 	}
  95.  
  96. 	bool empty(void) const {
  97. 		return (cnt == 0);
  98. 	}
  99.  
  100. private:
  101.  
  102. 	bool _alloc_array(size_t n){
  103. 		size_t tmem;
  104. 		if(arr == NULL){
  105. 			tmem = mem;
  106. 			if(n > tmem)
  107. 				tmem = n;
  108. 			arr = new (std::nothrow) T[tmem];
  109. 			if(arr == NULL)
  110. 				return false;
  111. 			mem = tmem;
  112. 		} else if((cnt + n) >= mem){
  113. 			tmem   = cnt + n + mem / 3;
  114. 			T* tmp = new (std::nothrow) T[tmem];
  115. 			if(tmp == NULL)
  116. 				return false;
  117.  
  118. 			T* p = tmp;
  119. 			T* e = arr + cnt;
  120. 			for(T* i = arr; i != e; ++i)
  121. 				*p++ = *i;
  122.  
  123. 			delete[] arr;
  124. 			arr = tmp;
  125. 			mem = tmem;
  126. 		}
  127. 		return true;
  128. 	}
  129.  
  130. 	void heapify(size_t i){
  131. 		size_t li, ri, big;
  132.  
  133. 		while(1) {
  134. 			li = (i << 1) + 1;
  135. 			ri = li + 1;
  136. 			if((li < cnt) && cmp(arr[li], arr[i]))
  137. 				big = li;
  138. 			else
  139. 				big = i;
  140.  
  141. 			if((ri < cnt) && cmp(arr[ri], arr[big]))
  142. 				big = ri;
  143.  
  144. 			if(big != i){
  145. 				std::swap(arr[big], arr[i]);
  146. 				i = big;
  147. 			}else
  148. 				break;
  149. 		}
  150. 	}
  151. };
  152.  
  153. // от наименьшего к большему
  154. struct intcmp {
  155. 	bool operator () (int a, int b)const{
  156. 		return (a < b);
  157. 	}
  158. };
  159.  
  160.  
  161. int main(void){
  162. 	pqueue<char> pch;
  163. 	for(int i = 0; i < 30; ++i)
  164. 		pch.push('A' + (char)(std::rand() % 26));	
  165.  
  166. 	while(! pch.empty()){
  167. 		std::cout << pch.top();
  168. 		pch.pop();
  169. 	}
  170. 	std::cout << std::endl;
  171.  
  172. 	//...
  173.  
  174. 	int A[] = { 5, 2, 8, 6, 7, 1, 9, 3, 0, 4 };
  175. 	pqueue<int, intcmp> pq(A, A + sizeof(A)/sizeof(A[0]));
  176.  
  177. 	while(! pq.empty()){
  178. 		std::cout << pq.top() << ' ';
  179. 		pq.pop();
  180. 	}
  181. 	return 0;
  182. }
Success #stdin #stdout 0s 3232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
ZYXWWSRRRQQONMLKKIHHDDDDCCBBBA
0 1 2 3 4 5 6 7 8 9
https://ideone.com/adpy8z
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!