fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. // 힙을 유지하기 위한 heapify 함수
  6. void heapify(vector<int>& arr, int n, int i) {
  7.     int largest = i;         // 루트를 가장 큰 값으로 가정
  8.     int left = 2 * i + 1;    // 왼쪽 자식
  9.     int right = 2 * i + 2;   // 오른쪽 자식
  10.  
  11.     // 왼쪽 자식이 루트보다 크다면
  12.     if (left < n && arr[left] > arr[largest])
  13.         largest = left;
  14.  
  15.     // 오른쪽 자식이 현재 가장 큰 값보다 크다면
  16.     if (right < n && arr[right] > arr[largest])
  17.         largest = right;
  18.  
  19.     // 가장 큰 값이 루트가 아니면 교환
  20.     if (largest != i) {
  21.         swap(arr[i], arr[largest]);
  22.         // 재귀적으로 힙 구조 유지
  23.         heapify(arr, n, largest);
  24.     }
  25. }
  26.  
  27. // 주어진 배열로부터 힙 생성
  28. void buildHeap(vector<int>& arr, int n) {
  29.     // 마지막 부모 노드부터 heapify 진행
  30.     for (int i = n / 2 - 1; i >= 0; i--) {
  31.         heapify(arr, n, i);
  32.     }
  33. }
  34.  
  35. // 힙 정렬 수행
  36. void heapSort(vector<int>& arr, int n) {
  37.     // 최대 힙 생성
  38.     buildHeap(arr, n);
  39.  
  40.     // 힙에서 하나씩 꺼내 정렬
  41.     for (int i = n - 1; i > 0; i--) {
  42.         // 현재 루트(최대값)를 끝으로 이동
  43.         swap(arr[0], arr[i]);
  44.         // 줄어든 힙에 대해 heapify
  45.         heapify(arr, i, 0);
  46.     }
  47. }
  48.  
  49. int main() {
  50.     vector<int> arr = {5, 10, 264, 362, 865, 63, 94, 475, 135, 932,
  51.                        25, 9, 33, 287, 332, 745, 377, 820, 62, 1};
  52.  
  53.     int n = arr.size();
  54.  
  55.     // 1. 힙 생성
  56.     vector<int> heapArr = arr;  // 복사
  57.     buildHeap(heapArr, n);
  58.  
  59.     cout << "1. 생성된 힙 배열: [";
  60.     for (int i = 0; i < n; i++) {
  61.         cout << heapArr[i];
  62.         if (i != n - 1) cout << ", ";
  63.     }
  64.     cout << "]\n";
  65.  
  66.     // 2. 힙 정렬
  67.     heapSort(arr, n);
  68.  
  69.     cout << "2. 정렬된 배열: [";
  70.     for (int i = 0; i < n; i++) {
  71.         cout << arr[i];
  72.         if (i != n - 1) cout << ", ";
  73.     }
  74.     cout << "]\n";
  75.  
  76.     return 0;
  77. }
  78.  
Success #stdin #stdout 0.01s 5260KB
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/xm1v0U
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!