fork download
copy 
  1. #include <iostream>
  2. #include <functional>
  3. #include <algorithm>
  4. #include <array>
  5.  
  6. template <std::size_t N, typename T = int, typename Comparator = std::less<T>>
  7. class NaryHeap {
  8. 	T* data;
  9. 	std::size_t heapSize, arraySize;
  10. 	const Comparator comparator;
  11. public:
  12. 	NaryHeap (std::size_t size) : data(new T[size]), heapSize(0), arraySize(size), comparator(Comparator{}) {}
  13. 	~NaryHeap() {delete[] data;}
  14. 	NaryHeap (const NaryHeap&);
  15. 	NaryHeap (NaryHeap&&);
  16. 	NaryHeap& operator= (const NaryHeap&);
  17. 	NaryHeap& operator= (NaryHeap&&);
  18. 	bool empty() const {return heapSize == 0;}
  19. 	T getMinimum() const {if (empty()) throw std::string("getMinimum() is invalid because the heap is empty.");  else return data[0];}
  20. 	void insert (const T& value);
  21. 	template <typename... Args> void insert (Args&&...);
  22. 	void removeMin() {removeHelper(0);}
  23. 	void remove (std::size_t nodeIndex);
  24. 	void removeByValue (const T&);
  25. 	void print() const;
  26. private:
  27. 	std::size_t getChildIndex (std::size_t n, std::size_t nodeIndex) const {return N * nodeIndex + n + 1;}  // The index of the nth child of the node with index 'nodeIndex'.  n takes on values from 0 to N-1.
  28. 	std::size_t getLeftChildIndex (std::size_t nodeIndex) const {return getChildIndex(0, nodeIndex);}  // The leftmost child.
  29. 	std::size_t getRightmostChildIndex (std::size_t nodeIndex) const {return std::min (heapSize - 1, getChildIndex(N-1, nodeIndex));}  // The rightmost child.
  30. 	std::size_t getParentIndex (std::size_t nodeIndex) const {return (nodeIndex - 1) / N;}  // This rounds down if nodeIndex - 1 is not a multiple of N.  Hence the returned value is the same regardless of which child the node is of the parent.
  31. 	void heapifyUp (std::size_t nodeIndex);
  32. 	void heapifyDown (std::size_t nodeIndex);
  33. 	void removeHelper (std::size_t nodeIndex, std::size_t lastNodeIndex); 
  34. 	void removeHelper (std::size_t nodeIndex) {removeHelper (nodeIndex, heapSize - 1);}
  35. 	bool isRoot (std::size_t nodeIndex) const {return nodeIndex == 0;}
  36. 	std::size_t indexOfFirstChildlessNode() const;
  37. 	std::size_t getMaxNodeIndex() const;
  38. };
  39.  
  40. template <std::size_t N, typename T, typename Comparator>
  41. NaryHeap<N, T, Comparator>::NaryHeap (const NaryHeap& other) : data(new T[other.arraySize]), heapSize(other.heapSize), arraySize(other.arraySize), comparator(other.comparator) {
  42. 	std::cout << "Copy constructor called.\n";
  43. 	for (std::size_t i = 0; i < heapSize; i++)
  44. 		data[i] = other.data[i];
  45. }
  46.  
  47. template <std::size_t N, typename T, typename Comparator>
  48. NaryHeap<N, T, Comparator>::NaryHeap (NaryHeap&& other) : data(other.data), heapSize(other.heapSize), arraySize(other.arraySize), comparator(other.comparator) {
  49. 	std::cout << "Move constructor called.\n";
  50. 	other.data = nullptr;
  51. 	other.heapSize = 0;
  52. 	other.arraySize = 0;
  53. }
  54.  
  55. template <std::size_t N, typename T, typename Comparator>
  56. NaryHeap<N, T, Comparator>& NaryHeap<N, T, Comparator>::operator= (const NaryHeap& other) {
  57. 	std::cout << "Assignment operator called.\n";
  58. 	if (other == *this)
  59. 		return *this;
  60. 	data = new T[other.arraySize];
  61. 	heapSize = other.heapSize;
  62. 	arraySize = other.arraySize;
  63. 	comparator = other.comparator;
  64. 	for (std::size_t i = 0; i < heapSize; i++)
  65. 		data[i] = other.data[i];
  66. 	return *this;
  67. }
  68.  
  69. template <std::size_t N, typename T, typename Comparator>
  70. NaryHeap<N, T, Comparator>& NaryHeap<N, T, Comparator>::operator= (NaryHeap&& other) {
  71. 	std::cout << "Move assignment operator called.\n";
  72. 	if (other == *this)
  73. 		return *this;
  74. 	data = other.data;
  75. 	heapSize = other.heapSize;
  76. 	arraySize = other.arraySize;
  77. 	comparator = other.comparator;
  78. 	other.data = nullptr;
  79. 	other.heapSize = 0;
  80. 	other.arraySize = 0;
  81. 	return *this;
  82. }
  83.  
  84. template <std::size_t N, typename T, typename Comparator>
  85. void NaryHeap<N, T, Comparator>::insert (const T& value) {
  86. 	if (heapSize == arraySize)
  87. 		throw std::string ("Heap's underlying storage is at maxiumum capacity.  Cannot insert.");
  88. 	data[heapSize] = value;
  89. 	heapifyUp(heapSize);	
  90. 	heapSize++;
  91. }
  92.  
  93. template <std::size_t N, typename T, typename Comparator>
  94. void NaryHeap<N, T, Comparator>::heapifyUp (std::size_t nodeIndex) {  // Recursively swap with parent node until the parent node's value is less than the node's value, or until the node has become the root of the heap. 
  95. 	if (isRoot(nodeIndex))
  96. 		return;
  97. 	const std::size_t parentIndex = getParentIndex(nodeIndex);
  98. 	if (comparator(data[nodeIndex], data[parentIndex])) {
  99. 		std::swap (data[nodeIndex], data[parentIndex]);  // Or 'const T temp = data[parentIndex];  data[parentIndex] = data[nodeIndex];  data[nodeIndex] = temp;' if swapping without using the algorithm library.
  100. 		heapifyUp(parentIndex);	
  101. 	}
  102. }
  103.  
  104. template <std::size_t N, typename T, typename Comparator>
  105. template <typename... Args>
  106. void NaryHeap<N, T, Comparator>::insert (Args&&... args) {
  107. 	const T a[] = {std::forward<Args>(args)...};
  108. 	for (std::size_t i = 0;  i < sizeof...(Args);  i++)
  109. 		insert(a[i]);
  110. }
  111.  
  112. template <std::size_t N, typename T, typename Comparator>
  113. void NaryHeap<N, T, Comparator>::removeHelper (std::size_t nodeIndex, std::size_t lastNodeIndex) {  // lastNodeIndex = heapSize - 1 by default.
  114. 	if (empty())
  115. 		throw std::string ("Cannot remove, because the heap is empty.");
  116. 	data[nodeIndex] = data[lastNodeIndex];
  117. 	heapSize--;
  118. 	heapifyDown(nodeIndex);  // There is no need to check 'if (heapSize > 0)' because heapSize == 0 would mean that leftChildIndex >= heapSize in the heapifyDown function, in which case returning out will happen.
  119. }
  120.  
  121. template <std::size_t N, typename T, typename Comparator>
  122. void NaryHeap<N, T, Comparator>::heapifyDown (std::size_t nodeIndex) {  // Recursively swap with the child node that has the smaller value until the parent child's value is less than the node's value, or until the node has no children. 
  123. 	const std::size_t leftChildIndex = getLeftChildIndex(nodeIndex);
  124. 	if (leftChildIndex >= heapSize)
  125. 		return;  // There are no children, so heapifyDown ends.
  126. 	const std::size_t childIndex = [=]() {  // Seeking the index among all the children of the node at position nodeIndex with the smallest T value. 
  127. 		std::size_t index = leftChildIndex;
  128. 		T minValue = data[leftChildIndex];
  129. 		const std::size_t rightmostChildIndex = getRightmostChildIndex(nodeIndex);
  130. 		for (std::size_t i = leftChildIndex + 1;  i < rightmostChildIndex;  i++)
  131. 			if (comparator(data[i], minValue)) {
  132. 				index = i;
  133. 				minValue = data[i];
  134. 			}
  135. 		return index;
  136. 	}();
  137. //	Below is another way of getting 'childIndex' (tested).  But on top of requiring '#include <vector>', building the 'indices' vector adds to the time complexity.
  138. //	const std::size_t rightmostChildIndex = getRightmostChildIndex(nodeIndex),  K = rightmostChildIndex - leftChildIndex + 1;
  139. //	std::vector<std::size_t> indices(K);
  140. //	for (std::size_t i = 0;  i < K;  i++)
  141. //		indices[i] = i + leftChildIndex;
  142. //	const std::size_t childIndex = *std::min_element (indices.begin(), indices.end(), [this](std::size_t x, std::size_t y) {return comparator(data[x], data[y]);});
  143. 	if (comparator(data[childIndex], data[nodeIndex])) {
  144.      	std::swap (data[childIndex], data[nodeIndex]);
  145.      	heapifyDown(childIndex);
  146.  	}
  147. }
  148.  
  149. template <std::size_t N, typename T, typename Comparator>
  150. void NaryHeap<N, T, Comparator>::remove (std::size_t nodeIndex) {
  151. 	removeHelper(nodeIndex, getMaxNodeIndex());
  152. }
  153.  
  154. template <std::size_t N, typename T, typename Comparator>
  155. std::size_t NaryHeap<N, T, Comparator>::indexOfFirstChildlessNode() const {
  156. 	// The following is a O(N) search.  A O(logN) search should exist and will be sought later.
  157. 	for (std::size_t i = 0;  i < heapSize;  i++)
  158. 		if (getLeftChildIndex(i) >= heapSize)
  159. 			return i;
  160. 	return heapSize - 1;
  161. }
  162.  
  163. template <std::size_t N, typename T, typename Comparator>
  164. std::size_t NaryHeap<N, T, Comparator>::getMaxNodeIndex() const {
  165. 	if (empty())
  166. 		throw std::string("getMinimum() is invalid because the heap is empty.");
  167. 	// The node with the largest value (using comparator) must be a node with no child, since the children of a node, by definition of heap, will have values larger than that node.
  168. 	const std::size_t firstIndex = indexOfFirstChildlessNode();
  169. 	std::size_t maxNodeIndex = firstIndex;
  170. 	T largestValue = data[firstIndex];
  171. 	for (std::size_t i = firstIndex + 1;  i < heapSize;  i++) {
  172. 		if (comparator(largestValue, data[i])) { 
  173. 			largestValue = data[i];
  174. 			maxNodeIndex = i;
  175. 		}
  176. 	}	
  177. 	return maxNodeIndex;
  178. }
  179.  
  180. template <std::size_t N, typename T, typename Comparator>
  181. void NaryHeap<N, T, Comparator>::removeByValue (const T& t) {
  182. 	for (int i = 0;  i < (int)heapSize;  i++)
  183. 		if (data[i] == t)
  184. 			return remove(i);
  185. }
  186.  
  187. template <std::size_t N, typename T, typename Comparator>
  188. void NaryHeap<N, T, Comparator>::print() const {
  189. 	for (std::size_t i = 0; i < heapSize; i++)
  190. 		std::cout << data[i] << ' ';
  191. 	std::cout << '\n';	
  192. }
  193.  
  194. template <typename T = int, typename Comparator = std::less<T>>
  195. using BinaryHeap = NaryHeap<2, T, Comparator>;
  196.  
  197. // Testing
  198. BinaryHeap<> createBinaryHeap() {
  199. 	BinaryHeap<> b(8);
  200. 	b.insert(7,6,5,4,3,2,1);
  201. 	return b;
  202. }
  203.  
  204. int main() {
  205. 	// A binary heap as a special case.
  206. 	BinaryHeap<int, std::greater<int>> binaryHeap(10);  // A max binary heap due to std::greater<int>.
  207. 	binaryHeap.insert(5);
  208. 	binaryHeap.insert(3,1,6,0,8,2,9,4,7);
  209. 	binaryHeap.print();  // 9 8 6 5 7 1 2 3 4 0
  210. 	binaryHeap.removeMin();
  211. 	binaryHeap.print();  // 8 7 6 5 0 1 2 3 4
  212. 	binaryHeap.removeMin();
  213. 	binaryHeap.print();  // 7 5 6 4 0 1 2 3
  214. 	binaryHeap.remove(5);  // Removes the node in the 5th position (i.e. removes the node with value 1).
  215. 	binaryHeap.print();  // 7 5 6 4 0 3 2
  216. 	binaryHeap.removeByValue(3);
  217. 	binaryHeap.print();  // 7 5 6 4 0 2
  218.  
  219. 	// A ternary heap.
  220. 	struct CompareCharacters {
  221. 		bool operator()(char x, char y) const {return (int)x < (int)y;}
  222. 	};
  223.  
  224. 	NaryHeap<3, char, CompareCharacters> ternaryHeap(10);  // The default std::less<char> does the same thing as CompareCharacters actually.
  225. 	ternaryHeap.insert('b','c','e','a','g','d','j','i','h');
  226. 	ternaryHeap.print();  // a c e b g d j i h  (the 3 children of a are c,e,b, and the 3 children of c are g,d,j, and the 2 children of e are i,h).
  227. 	ternaryHeap.removeMin();
  228. 	ternaryHeap.print();  // c d e b g h j i
  229. 	ternaryHeap.remove(4);
  230. 	ternaryHeap.print();  // c d e b i h j
  231. 	ternaryHeap.removeByValue('i');
  232. 	ternaryHeap.print();  // c d e b j h
  233. 	ternaryHeap.removeByValue('z');
  234. 	ternaryHeap.print();  // c d e b j h  (since 'z' does not exist in the heap)
  235.  
  236. 	NaryHeap<3, char, CompareCharacters> heap = ternaryHeap;  // "Copy constructor called."
  237. 	heap.print();  // c d e b j h
  238.  
  239. 	BinaryHeap<> b = createBinaryHeap();
  240. 	b.print();  // 1 4 2 7 5 6 3
  241. }
  242.  
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
9 8 6 5 7 1 2 3 4 0 
8 5 6 3 7 1 2 0 4 
5 4 6 3 7 1 2 0 
5 4 6 3 7 0 2 
5 4 6 0 7 0 
a c e b g d j i h 
c d e b g h j i 
c d e b j h j 
c d e b j h j 
c d e b j h j 
Copy constructor called.
c d e b j h j 
1 4 2 7 5 6 3
https://ideone.com/C4JfZB
language:
C++14 (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!