编程练习——堆Heap

Posted on Edited on Word count in article: 2.2k Reading time ≈ 2 mins.

因为vs2005中c++的Heap构造 _ 有些问题 _
 ，所以才重写了heap类。

不知道vs2008中这个是不是个bug。

  1. /* created by chico chen
  2. *  date 2008/10/25
  3. */
  4. template< class T, class Cmp>
  5. class Heap
  6. {
  7. private :
  8. vector heap;
  9. void ShiftDown( int index)
  10. {
  11. while (!IsLeaf(index))
  12. {
  13. int l = Lchild(index);
  14. int r = Rchild(index);
  15. if (r != -1)
  16. {
  17. if (Cmp::Up(heap[r],heap[l]))
  18. {
  19. // put the up node to the left
  20. swap(heap[l],heap[r]);
  21. }
  22. }
  23. if (Cmp::Up(heap[l],heap[index]))
  24. {
  25. // up the left child
  26. swap(heap[l],heap[index]);
  27. index = l;
  28. }
  29. else
  30. {
  31. break ;
  32. }
  33. }
    1. }
  35. void ShiftUp( int index)
  36. {
  37. int parent = -1;
  38. while (index != 0)
  39. {
  40. parent = Parent(index);
  41. if (Cmp::Up(heap[index],heap[parent]))
  42. {
  43. swap(heap[index],heap[parent]);
  44. index = parent;
  45. }
  46. else
  47. {
  48. break ;
  49. }
  50. }
    1. }
  52. void ReHeapAll()
  53. {
  54. for ( int i=Parent(heap.size()-1); i>= 0; i–)
  55. {
  56. ShiftDown(i);
  57. }
  58. }
  59. void ReHeapOne( int index)
  60. // set one prior and re-position the index node
  61. {
  62. T data = heap[index];
  63. ShiftDown(index);
  64. if (Cmp::Eq(data,heap[index]))
  65. {
  66. ShiftUp(index);
  67. }
  68. }
  69. int Parent( int index)
  70. // parent node of the index node
  71. {
  72. return (index-1)/2;
  73. }
  74. int Lchild( int index)
  75. // Left child of the index node
  76. {
  77. if (!IsLeaf(index))
  78. return index*2+1;
  79. return -1;
  80. }
  81. int Rchild( int index)
  82. // Right child of the index node
  83. {
  84. if (!IsLeaf(index))
  85. {
  86. int r= index*2+2;
  87. if (r<heap.size())
  88. return r;
  89. }
  90. return -1;
  91. }
    1. int IsLeaf( int index)
  93. {
  94. assert(index < heap.size());
  95. if (heap.size() == 1)
  96. return true ;
  97. int lastNode = Parent(heap.size()-1);
  98. return lastNode < index;
  99. }
    1. int FindData(T& data)
  101. {
  102. int len = heap.size();
  103. for ( int i = 0; i < len; i++)
  104. {
  105. if (Cmp::Eq(data,heap[i]))
  106. {
  107. return i;
  108. }
  109. }
  110. return -1; // can not find the data
  111. }
    1. void printTree( int index, int count)
  113. {
  114. if (index < heap.size() && index >=0)
  115. {
    1. printTree(Rchild(index),count+4);
  117. for ( int i = 0; i < count; i++)
  118. {
  119. cout << " " ;
  120. }
  121. cout <<heap[index]<<endl;
  122. printTree(Lchild(index),count+4);
  123. }
  124. }
  125. public :
  126. Heap()
  127. {
  128. heap = vector();
  129. }
  130. ~Heap()
  131. {
  132. // heap destroyed
  133. }
  134. bool IsEmpty()
  135. {
  136. return heap.size() == 0;
  137. }
        1. void Insert(T& data)
  139. {
  140. heap.push_back(data);
  141. ShiftUp(heap.size()-1);
  142. }
  143. void Delete( int index)
  144. {
  145. int last = heap.size()-1;
  146. if (index>=0 && index <= last)
  147. {
    1. swap(heap[index],heap[last]);
  149. heap.pop_back();
  150. ReHeapOne(index);
  151. }
  152. }
  153. void Delete(T& data)
  154. {
  155. int index = FindData(data);
  156. if (index != -1)
  157. Delete(index);
  158. }
      1. void RemoveTop()
  160. {
    1. if (!IsEmpty()&&heap.size()>1)
  162. {
  163. swap(heap[0],heap[heap.size()-1]);
  164. heap.pop_back();
  165. ShiftDown(0);
  166. }
  167. else if (heap.size() == 1)
  168. {
  169. heap.pop_back();
  170. }
    1. }
  172. T& Top()
  173. {
  174. return heap[0];
  175. }
    1. void Print()
  177. {
  178. printTree(0,1);
  179. }
        1. };