Posted By

gasfusion on 02/21/10


Tagged

minmax heap


Versions (?)

MinMax Heap


 / Published in: C++
 

This implementation is part of a larger project and has a dependency on a Stopwatch class, which was used to measure CPU cycles for heap operations. I am not stripping it out as it is easy to remove this dependency without much effort. To use, create a new heap object with the type type of your choice. Pass it the array to heapify along with its current size and maxium size.

  1. /* HEADER */
  2.  
  3. #pragma once
  4. #include "Stopwatch\stopwatch.h"
  5. #include <math.h>
  6. #include <string>
  7. using namespace std;
  8.  
  9. template <class Type>
  10. class MinMaxHeap
  11. {
  12. public:
  13. /* Constructor */
  14. MinMaxHeap(Type *array, const int mSize, const int cSize);
  15.  
  16. /* Destructor */
  17. ~MinMaxHeap();
  18.  
  19. /* Accessors */
  20. void getFirstTenElements() const;
  21. void getLastTenElements() const;
  22. int getNumOfComparisons() const;
  23. double getCpuCycles() const;
  24.  
  25. private:
  26. /* Variables */
  27. Type *Heap; // MinMaxHeap array
  28. int curSize, maxSize; // Heap current size, Heap max Size
  29. int compCount; // Holds number of comparisons per run
  30. double cpuTime; // Holds the number of cpu cycles
  31.  
  32. /* Modifiers */
  33. void buildMinMaxHeap();
  34. void percolateDown(const int pos);
  35. void percolateDownMax( const int pos );
  36. void percolateDownMin( const int pos );
  37. void swap(const int indexOne, const int indexTwo);
  38.  
  39. /* Accessors */
  40. bool isMaxLevel(const int pos);
  41. int GetMaxGrandChild(int pos);
  42. int GetMinGrandChild(int pos);
  43. bool isLeafPos(int pos);
  44. int GetMaxDescendant(int pos);
  45. int GetMinDescendant(int pos);
  46. };
  47.  
  48. #include "MinMaxHeap.cpp"
  49.  
  50. /* IMPLEMENTATION */
  51.  
  52. #include "MinMaxHeap.h"
  53.  
  54. /* Gets the heap structure and heapifies it. */
  55. template <class Type>
  56. MinMaxHeap<Type>::MinMaxHeap(Type *array, const int mSize, const int cSize)
  57. {
  58. Heap = array;
  59. curSize = cSize;
  60. maxSize = mSize;
  61. compCount = 0;
  62. buildMinMaxHeap();
  63. }
  64.  
  65. /* Deallocated memory allocated for the Heap. */
  66. template <class Type>
  67. MinMaxHeap<Type>::~MinMaxHeap()
  68. {
  69. if (Heap != NULL)
  70. delete [] Heap;
  71. }
  72.  
  73. /* Prints the first 10 elements of the heap. */
  74. template <class Type>
  75. void MinMaxHeap<Type>::getFirstTenElements() const
  76. {
  77. int max = 10;
  78. if (curSize < max)
  79. max = curSize;
  80. for (int i=0;i<max;i++)
  81. cout << Heap[i] << " ";
  82. }
  83.  
  84. /* Prints the last 10 elements of the heap. */
  85. template <class Type>
  86. void MinMaxHeap<Type>::getLastTenElements() const
  87. {
  88. int max = 10;
  89. if (curSize < max)
  90. max = curSize;
  91. for (int i=curSize-max;i<curSize;i++)
  92. cout << Heap[i] << " ";
  93. }
  94.  
  95. /* Returns the number of comparisons made during the heapify process. */
  96. template <class Type>
  97. int MinMaxHeap<Type>::getNumOfComparisons() const
  98. {
  99. return compCount;
  100. }
  101.  
  102. /* Returns the number of cycles for the heapify process. */
  103. template <class Type>
  104. double MinMaxHeap<Type>::getCpuCycles() const
  105. {
  106. return cpuTime;
  107. }
  108.  
  109. /* Returns the maximum grandchild of a position. */
  110. template <class Type>
  111. int MinMaxHeap<Type>::GetMaxGrandChild(int pos)
  112. {
  113. /* Initializing values */
  114. bool maxValInit = false;
  115. Type maxVal;
  116. int maxIndex = pos;
  117. int curIndex;
  118.  
  119. /* Get a grandchild */
  120. curIndex = 2*(2*pos);
  121.  
  122. /* Check for valid position */
  123. compCount++;
  124. if (curIndex <= curSize)
  125. {
  126. /* Check if maxVal isn't initialized or
  127.   /* current index is greater than maxVal
  128.   /*/
  129. compCount++;
  130. if ((!maxValInit) || (Heap[curIndex] > maxVal))
  131. {
  132. maxIndex = curIndex;
  133. maxVal = Heap[maxIndex];
  134. maxValInit = true;
  135. }
  136. }
  137.  
  138. /* Get the other grandchild */
  139. curIndex = 2*((2*pos)+1);
  140. compCount++;
  141. if (curIndex <= curSize)
  142. {
  143. compCount++;
  144. if ((!maxValInit) || (Heap[curIndex] > maxVal))
  145. {
  146. maxIndex = curIndex;
  147. maxVal = Heap[maxIndex];
  148. maxValInit = true;
  149. }
  150. }
  151.  
  152. curIndex = 2*(2*pos)+1;
  153. compCount++;
  154. if (curIndex <= curSize)
  155. {
  156. compCount++;
  157. if ((!maxValInit) || (Heap[curIndex] > maxVal))
  158. {
  159. maxIndex = curIndex;
  160. maxVal = Heap[maxIndex];
  161. maxValInit = true;
  162. }
  163. }
  164.  
  165. curIndex = (2*((2*pos)+1))+1;
  166. compCount++;
  167. if (curIndex <= curSize)
  168. {
  169. compCount++;
  170. if ((!maxValInit) || (Heap[curIndex] > maxVal))
  171. {
  172. maxIndex = curIndex;
  173. maxVal = Heap[maxIndex];
  174. maxValInit = true;
  175. }
  176. }
  177. return maxIndex;
  178. }
  179.  
  180. /* Returns the position of the minimum */
  181. template <class Type>
  182. int MinMaxHeap<Type>::GetMinGrandChild(int pos)
  183. {
  184. bool maxValInit = false;
  185. Type minVal;
  186. int minIdx = pos;
  187. int curIndex;
  188.  
  189. curIndex = 2*(2*pos);
  190. compCount++;
  191. if (curIndex <= curSize)
  192. {
  193. compCount++;
  194. if ((!maxValInit) || (Heap[curIndex] < minVal))
  195. {
  196. minIdx = curIndex;
  197. minVal = Heap[minIdx];
  198. maxValInit = true;
  199. }
  200. }
  201.  
  202. curIndex = 2*((2*pos)+1);
  203. compCount++;
  204. if (curIndex <= curSize)
  205. {
  206. compCount++;
  207. if ((!maxValInit) || (Heap[curIndex] < minVal))
  208. {
  209. minIdx = curIndex;
  210. minVal = Heap[minIdx];
  211. maxValInit = true;
  212. }
  213. }
  214.  
  215. curIndex = 2*(2*pos)+1;
  216. compCount++;
  217. if (curIndex <= curSize)
  218. {
  219. compCount++;
  220. if ((!maxValInit) || (Heap[curIndex]<minVal))
  221. {
  222. minIdx = curIndex;
  223. minVal = Heap[minIdx];
  224. maxValInit = true;
  225. }
  226. }
  227.  
  228. curIndex = (2*((2*pos)+1))+1;
  229. compCount++;
  230. if (curIndex <= curSize)
  231. {
  232. compCount++;
  233. if ((!maxValInit) || (Heap[curIndex] < minVal))
  234. {
  235. minIdx = curIndex;
  236. minVal = Heap[minIdx];
  237. maxValInit = true;
  238. }
  239. }
  240. return minIdx;
  241. }
  242.  
  243. /* Returns the maximum child of a position. */
  244. template <class Type>
  245. int MinMaxHeap<Type>::GetMaxDescendant(int pos)
  246. {
  247. bool maxValInit = false;
  248. Type maxVal;
  249. int maxIndex = pos;
  250. int curIndex;
  251.  
  252. maxIndex = GetMaxGrandChild(pos);
  253. compCount++;
  254. if (maxIndex != pos)
  255. {
  256. maxVal = Heap[maxIndex];
  257. maxValInit = false;
  258. }
  259.  
  260. curIndex = 2*pos;
  261. compCount++;
  262. if ((curIndex <= curSize)&&(isLeafPos(curIndex)))
  263. {
  264. compCount++;
  265. if ((!maxValInit)||(Heap[curIndex] > maxVal))
  266. {
  267. maxIndex = curIndex;
  268. maxVal = Heap[curIndex];
  269. maxValInit = true;
  270. }
  271. }
  272.  
  273. curIndex = (2*pos)+1;
  274. compCount++;
  275. if ((curIndex <= curSize)&&(isLeafPos(curIndex)))
  276. {
  277. compCount++;
  278. if ((!maxValInit)||(Heap[curIndex] > maxVal))
  279. {
  280. maxIndex = curIndex;
  281. maxVal = Heap[curIndex];
  282. maxValInit = true;
  283. }
  284. }
  285. return maxIndex;
  286. }
  287.  
  288. /* Returns the minimum element of a position. */
  289. template <class Type>
  290. int MinMaxHeap<Type>::GetMinDescendant(int pos) // opposite of GetMaxDescendant Idx
  291. {
  292. bool maxValInit = false;
  293. Type minVal;
  294. int minIdx = pos;
  295. int curIndex;
  296.  
  297. minIdx = GetMinGrandChild(pos);
  298. compCount++;
  299. if (minIdx != pos)
  300. {
  301. minVal = Heap[minIdx];
  302. maxValInit = true;
  303. }
  304.  
  305. curIndex = 2*pos;
  306. compCount++;
  307. if ((curIndex <= curSize)&&(isLeafPos(curIndex)))
  308. {
  309. compCount++;
  310. if ((!maxValInit)||(Heap[curIndex] < minVal))
  311. {
  312. minIdx = curIndex;
  313. minVal = Heap[curIndex];
  314. maxValInit = true;
  315. }
  316. }
  317.  
  318. curIndex = (2*pos)+1;
  319. compCount++;
  320. if ((curIndex <= curSize)&&(isLeafPos(curIndex)))
  321. {
  322. compCount++;
  323. if ((!maxValInit)||(Heap[curIndex] < minVal))
  324. {
  325. minIdx = curIndex;
  326. minVal = Heap[curIndex];
  327. maxValInit = true;
  328. }
  329. }
  330. return minIdx;
  331. }
  332.  
  333. /* Perculates down maximum levels until a position is in its correct location.
  334.  */
  335. template <class Type>
  336. bool MinMaxHeap<Type>::isLeafPos(int pos)
  337. {
  338. bool isLeaf = false;
  339. compCount++;
  340. if ((2*pos > curSize) && ((2*pos)+1 > curSize))
  341. isLeaf = true;
  342. return isLeaf;
  343. }
  344.  
  345.  
  346. /* Builds the Min-Max Heap Tree. */
  347. template <class Type>
  348. void MinMaxHeap<Type>::buildMinMaxHeap()
  349. {
  350. Stopwatch myWatch;
  351. myWatch.start();
  352. for ( int i = curSize/2; i >= 0; i--)
  353. percolateDown(i);
  354. myWatch.stop();
  355. cpuTime = myWatch.get_end_time();
  356. }
  357.  
  358. /* Determines the level of a position and percolates it down maximum if level /* is max and percolates down minimum if level is min.
  359.  */
  360. template <class Type>
  361. void MinMaxHeap<Type>::percolateDown(const int pos)
  362. {
  363. if (isMaxLevel(pos))
  364. percolateDownMax( pos );
  365. else
  366. percolateDownMin( pos );
  367. }
  368.  
  369. /* Perculates down minimum levels until a position is in its correct location.
  370.  */
  371. template <class Type>
  372. void MinMaxHeap<Type>::percolateDownMin(const int pos)
  373. {
  374. /* Find the smallest child/grandchild position */
  375. int minPos = GetMinDescendant(pos);
  376.  
  377. /* Check if we have a child */
  378. compCount++;
  379. if (minPos > 0)
  380. {
  381. /* Check if minimum is a grandchild */
  382. compCount++;
  383. if (minPos >= pos * 4)
  384. {
  385. /* Swap if less than grandparent */
  386. compCount++;
  387. if (Heap[minPos] < Heap[pos])
  388. {
  389. swap(pos, minPos);
  390.  
  391. /* Swap if greater than parent */
  392. compCount++;
  393. if (Heap[minPos] > Heap[minPos/2])
  394. swap(minPos, minPos/2);
  395. percolateDownMin( minPos );
  396. }
  397. }
  398. /* We don't have a grandchild */
  399. else
  400. {
  401. /* Swap if less than parent */
  402. compCount++;
  403. if (Heap[minPos] < Heap[pos])
  404. swap(pos, minPos);
  405. }
  406. }
  407. }
  408.  
  409.  
  410. /* Perculates down maximum levels until a position is in its correct location. */
  411. template <class Type>
  412. void MinMaxHeap<Type>::percolateDownMax( const int pos )
  413. {
  414. /* Find maximum child/grandchild */
  415. //int maxPos = getMaximumChild(pos*2, pos*4);
  416. int maxPos = GetMaxDescendant(pos);
  417.  
  418. /* Check if we have a child */
  419. compCount++;
  420. if (maxPos > 0)
  421. {
  422. /* Check if position is a grandchild */
  423. compCount++;
  424. if (maxPos >= pos * 4)
  425. {
  426. /* Swap if greater than grandparent */
  427. compCount++;
  428. if (Heap[maxPos] > Heap[pos])
  429. {
  430. swap(pos, maxPos);
  431.  
  432. /* Swap if less than parent */
  433. compCount++;
  434. if (Heap[maxPos] < Heap[maxPos/2])
  435. swap(maxPos, maxPos/2);
  436. percolateDownMax( maxPos );
  437. }
  438. }
  439. /* Position is a child */
  440. else
  441. {
  442. /* Swap if greater than parent */
  443. compCount++;
  444. if (Heap[maxPos] > Heap[pos])
  445. swap(pos, maxPos);
  446. }
  447. }
  448. }
  449.  
  450. /* Returns true if a position is on maximum level and false if it is not. */
  451. template <class Type>
  452. bool MinMaxHeap<Type>::isMaxLevel(const int pos)
  453. {
  454. return (int) (log(pos+1.0)/log(2.0))%2 == 1;
  455. }
  456.  
  457.  
  458. /* Swaps elements in the Heap array using two positions. */
  459. template <class Type>
  460. void MinMaxHeap<Type>::swap(const int indexOne,const int indexTwo)
  461. {
  462. Type tmp = Heap[ indexOne ];
  463. Heap[ indexOne ] = Heap[ indexTwo ];
  464. Heap[ indexTwo ] = tmp;
  465. }

Report this snippet  

You need to login to post a comment.