fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. void heapify(vector<int>& arr, int n, int i) {
  6.     int largest = i;
  7.     int left = 2 * i + 1;
  8.     int right = 2 * i + 2;
  9.  
  10.     if (left < n && arr[left] > arr[largest])
  11.         largest = left;
  12.  
  13.     if (right < n && arr[right] > arr[largest])
  14.         largest = right;
  15.  
  16.     if (largest != i) {
  17.         swap(arr[i], arr[largest]);
  18.         heapify(arr, n, largest);
  19.     }
  20. }
  21.  
  22. void buildHeap(vector<int>& arr, int n) {
  23.     for (int i = n / 2 - 1; i >= 0; i--) {
  24.         heapify(arr, n, i);
  25.     }
  26. }
  27.  
  28. void heapSort(vector<int>& arr, int n) {
  29.     buildHeap(arr, n);
  30.  
  31.     for (int i = n - 1; i > 0; i--) {
  32.         swap(arr[0], arr[i]);
  33.         heapify(arr, i, 0);
  34.     }
  35. }
  36.  
  37. int main() {
  38.     vector<int> arr = {5, 10, 264, 362, 865, 63, 94, 475, 135, 932,
  39.                        25, 9, 33, 287, 332, 745, 377, 820, 62, 1};
  40.  
  41.     int n = arr.size();
  42.  
  43.     // 1. 힙 생성
  44.     vector<int> heapArr = arr;  // 복사
  45.     buildHeap(heapArr, n);
  46.  
  47.     cout << "1. 생성된 힙 배열: [";
  48.     for (int i = 0; i < n; i++) {
  49.         cout << heapArr[i];
  50.         if (i != n - 1) cout << ", ";
  51.     }
  52.     cout << "]\n";
  53.  
  54.     // 2. 힙 정렬
  55.     heapSort(arr, n);
  56.  
  57.     cout << "2. 정렬된 배열: [";
  58.     for (int i = 0; i < n; i++) {
  59.         cout << arr[i];
  60.         if (i != n - 1) cout << ", ";
  61.     }
  62.     cout << "]\n";
  63.  
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1. 생성된 힙 배열: [932, 865, 332, 820, 25, 63, 287, 745, 362, 10, 5, 9, 33, 264, 94, 475, 377, 135, 62, 1]
2. 정렬된 배열: [1, 5, 9, 10, 25, 33, 62, 63, 94, 135, 264, 287, 332, 362, 377, 475, 745, 820, 865, 932]
https://ideone.com/byTtbB
language:
C++ (gcc 8.3)
created:
4 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!