fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // define maximum capacity of heap
  5. #define N 100
  6.  
  7. // Data structure for Max Heap
  8. struct PriorityQueue
  9. {
  10. private:
  11. 	// array of size N to store heap elements
  12.     int A[N];
  13.  
  14. 	// stores current size of heap data
  15.     unsigned size = 0;
  16.  
  17.     // return parent of A[i]
  18.     // don't call this function if it is already a root node
  19.     int PARENT(int i) 
  20.     { 
  21.         return (i - 1) / 2; 
  22.     }
  23.  
  24.     // return left child of A[i]    
  25.     int LEFT(int i) 
  26.     { 
  27.         return (2 * i + 1); 
  28.     }
  29.  
  30.     // return right child of A[i]   
  31.     int RIGHT(int i) 
  32.     { 
  33.         return (2 * i + 2); 
  34.     }
  35.  
  36.     // Recursive Heapify-down algorithm
  37.     // the node at index i and its two direct children
  38.     // violates the heap property
  39.     void heapify_down(int i)
  40.     {
  41.         // get left and right child of node at index i
  42.         unsigned left = LEFT(i);
  43.         unsigned right = RIGHT(i);
  44.  
  45.         int largest = i;
  46.  
  47.         // compare A[i] with its left and right child
  48.         // and find largest value
  49.         if (left < size && A[left] > A[i])
  50.             largest = left;
  51.  
  52.         if (right < size && A[right] > A[largest])
  53.             largest = right;
  54.  
  55.         // swap with child having greater value and 
  56.         // call heapify-down on the child
  57.         if (largest != i) {
  58.             swap(A[i], A[largest]);
  59.             heapify_down(largest);
  60.         }
  61.     }
  62.  
  63.     // Recursive Heapify-up algorithm
  64.     void heapify_up(int i)
  65.     {
  66.         // check if node at index i and its parent violates 
  67.         // the heap property
  68.         if (i && A[PARENT(i)] < A[i]) 
  69.         {
  70.             // swap the two if heap property is violated
  71.             swap(A[i], A[PARENT(i)]);
  72.  
  73.             // call Heapify-up on the parent
  74.             heapify_up(PARENT(i));
  75.         }
  76.     }
  77.  
  78. public:
  79.  
  80. 	// return size of the heap
  81.     unsigned heapSize()
  82.     {
  83.         return size;
  84.     }
  85.  
  86.     // function to check if heap is empty or not
  87.     int empty()
  88.     {
  89.         return size == 0;
  90.     }
  91.  
  92. 	// insert key into the heap
  93. 	void push(int key)
  94. 	{
  95. 		// if heap is full, return
  96. 		if (size == N) {
  97. 			printf("Heap overflow\n");
  98. 			return;
  99. 		}
  100.  
  101. 		// insert the new element to the end of the array
  102. 		int i = size;
  103. 		A[i] = key;
  104.  
  105. 		// call heapify-up procedure
  106.         heapify_up(i);
  107.  
  108. 		// increment size of heap by 1
  109. 		size++;
  110. 	}
  111.  
  112. 	// function to remove element with highest priority (present at root)
  113. 	void pop()
  114. 	{
  115. 		// if heap has no elements
  116. 		if (size <= 0) {
  117. 			printf("Heap underflow\n");
  118. 			return;
  119. 		}
  120.  
  121. 		// replace the root of the heap with the last element
  122.         // of the array
  123. 		A[0] = A[size-1];
  124.  
  125. 		// decrease heap size by 1
  126. 		size--;
  127.  
  128. 		// call heapify-down on root node
  129. 		heapify_down(0);
  130. 	}
  131.  
  132. 	// function to return element with highest priority (present at root)	
  133. 	int top() 
  134. 	{
  135. 		// if heap has no elements
  136. 		if (size <= 0)
  137. 		{
  138. 			printf("Heap underflow\n");
  139. 			return -1;
  140. 		}
  141. 		// else return the root (first) element
  142. 		return A[0]; 
  143. 	}
  144.  
  145. };
  146.  
  147. int main(void)
  148. {
  149. 	PriorityQueue pq;
  150.  
  151.     // Note - Priority is decided by element's value
  152.  
  153.     pq.push(3);
  154.     pq.push(2);
  155.     pq.push(15);
  156.  
  157.     printf("Size is %d\n", pq.heapSize()); 
  158.  
  159.     printf("%d ", pq.top());
  160.     pq.pop();
  161.  
  162.     printf("%d ", pq.top());
  163.     pq.pop();
  164.  
  165.     pq.push(5);
  166.     pq.push(4);
  167.     pq.push(45);
  168.  
  169.     printf("Size is %d\n", pq.heapSize()); 
  170.  
  171.     printf("%d ", pq.top());
  172.     pq.pop();
  173.  
  174.     printf("%d ", pq.top());
  175.     pq.pop();
  176.  
  177.     printf("%d ", pq.top());
  178.     pq.pop();
  179.  
  180.     printf("%d ", pq.top());
  181.     pq.pop();
  182.  
  183. 	if (pq.empty())
  184. 		printf("\nHeap is empty\n");
  185.  
  186.     pq.top();   // top operation on an empty heap
  187.     pq.pop();   // pop operation on an empty heap
  188.  
  189.     return 0;
  190. }
  191.  
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Size is 3
15 3 Size is 4
45 5 4 2 
Heap is empty
Heap underflow
Heap underflow
https://ideone.com/2UNCN3
Max Heap implementation
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!