fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. const int MAX_SIZE = 1000;
  5. int heap[MAX_SIZE];
  6. int heapSize = 0;
  7.  
  8. int parent(int i) { return (i - 1) / 2; }
  9. int leftChild(int i) { return 2 * i + 1; }
  10. int rightChild(int i) { return 2 * i + 2; }
  11.  
  12. void heapifyUp(int i) {
  13.     while (i > 0 && heap[parent(i)] > heap[i]) {
  14.         swap(heap[i], heap[parent(i)]);
  15.         i = parent(i);
  16.     }
  17. }
  18.  
  19. void heapifyDown(int i) {
  20.     int smallest = i;
  21.     int left = leftChild(i);
  22.     int right = rightChild(i);
  23.  
  24.     if (left < heapSize && heap[left] < heap[smallest])
  25.         smallest = left;
  26.     if (right < heapSize && heap[right] < heap[smallest])
  27.         smallest = right;
  28.  
  29.     if (smallest != i) {
  30.         swap(heap[i], heap[smallest]);
  31.         heapifyDown(smallest);
  32.     }
  33. }
  34.  
  35. void insert(int value) {
  36.     if (heapSize >= MAX_SIZE) {
  37.         cout << "Heap đầy!" << endl;
  38.         return;
  39.     }
  40.     heap[heapSize] = value;
  41.     heapifyUp(heapSize);
  42.     heapSize++;
  43. }
  44.  
  45. int extractMin() {
  46.     if (heapSize <= 0) {
  47.         cout << "Heap rỗng!" << endl;
  48.         return -1;
  49.     }
  50.     int root = heap[0];
  51.     heap[0] = heap[--heapSize];
  52.     heapifyDown(0);
  53.     return root;
  54. }
  55.  
  56. void printHeap() {
  57.     cout << "Min Heap hiện tại: ";
  58.     for (int i = 0; i < heapSize; i++) {
  59.         cout << heap[i] << " ";
  60.     }
  61.     cout << endl;
  62. }
  63.  
  64. int main() {
  65.     insert(10);
  66.     insert(5);
  67.     insert(3);
  68.     insert(2);
  69.     insert(8);
  70.     insert(15);
  71.  
  72.     printHeap();
  73.  
  74.     cout << "Phần tử nhỏ nhất (extractMin): " << extractMin() << endl;
  75.  
  76.     printHeap();
  77.  
  78.     return 0;
  79. }
  80.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Min Heap hiện tại: 2 3 5 10 8 15 
Phần tử nhỏ nhất (extractMin): 2
Min Heap hiện tại: 3 8 5 10 15
https://ideone.com/0wx9jo
language:
C++ (gcc 8.3)
created:
3 days 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!