[힙과 힙정렬] 힙생성 (순차힙, 최대힙)

[힙과 힙정렬] 힙생성 (순차힙, 최대힙)

[힙 생성]

1. 삽입식 >> 모든 키들이 미리 주어진 경우, 또는 키들이 차례로 주어지는 경우 적용 가능

2. 상향식 >> 모든 키들이 미리 주어진 경우만 적용 가능

1. 삽입식 힙 생성

#include #include int H[99]; // 힙 배열 int n = 0; // 힙의 크기 void upHeap(int i) {// ket 삽입 후 정렬하는 함수 int tmp; if (i == 1) return; if (H[i] <= H[i / 2]) // i가 root가 아닐 때 부모노드보다 작으면 그대로 반환 return; // i가 부모노드보다 크다면 swap해주기 tmp = H[i]; H[i] = H[i / 2]; H[i / 2] = tmp; upHeap(i / 2);// 부모노드가 바꼈으니까 다시 호출해서 그 부모노드의 부모노드와 값 비교해주기 } void downHeap(int i) {// 최대힙 반환 후 정렬하는 함수 int left = i * 2; //왼쪽 자식노드 인덱스, i는 1로 호출됐기 때문에 root int right = i * 2 + 1; // 오른쪽 자식노드 인덱스 int max, tmp; //max값 if (n < left && n < right)// 자식노드가 둘다 없다면 반환 return; max = left;// 아니라면 max에 왼쪽 자식노드 인덱스를 넣음 if (n >= right) {// 오른쪽 자식노드도 있다면 if (H[max] < H[right]) {//그리고 왼쪽 자식노드 값보다 오른쪽 자식노드 값이 크다면 max = right;// max에 오른쪽 자식노드 인덱스를 저장 } } if (H[max] <= H[i])// max에는 왼쪽 or 오른쪽 자식노드 인덱스가 들어있음, 그 값이 root값보다 적다면 그냥 반환 return; // 아니라면 == 왼쪽 or 오른쪽 자식노드 값이 root값보다 크다면 swap tmp = H[i]; H[i] = H[max]; H[max] = tmp; downHeap(max); } void insertItem(int key) { n += 1; H[n] = key; upHeap(n); } int removeMax() {//최대힙 반환 및 삭제 int key; key = H[1]; H[1] = H[n]; n -= 1; downHeap(1); return key; } void printHeap() { for (int i = 1; i <= n; i++) { printf(" %d", H[i]); } printf("

"); } int main() { char type; int key; while (1) { scanf("%c", &type;); if (type == 'q') break; else if (type == 'i') { scanf("%d", &key;); insertItem(key); printf("0

"); } else if (type == 'd') { printf("%d

", removeMax()); } else if (type == 'p') { printHeap(); } } return 0; }

2. 상향식 힙 생성

#include #include int H[99]; // 힙 배열 int n; // 힙의 크기 void downHeap(int i) { int left = i * 2; int right = i * 2 + 1; int max, tmp; if (n < left && n < right) return; max = left; if (n >= right) { if (H[max] < H[right]) { max = right; } } if (H[max] <= H[i]) return; tmp = H[i]; H[i] = H[max]; H[max] = tmp; downHeap(max); } void rBuildHeap(int i) { if (i > n) return; rBuildHeap(i * 2); rBuildHeap(i * 2 + 1); downHeap(i); return; } void printHeap() { for (int i = 1; i <= n; i++) { printf(" %d", H[i]); } printf("

"); } int main() { int i; scanf("%d", &n;); for (int i = 1; i <= n; i++) { scanf("%d", &H;[i]); getchar(); } rBuildHeap(1); printHeap(); return 0; }

from http://code731.tistory.com/26 by ccl(A) rewrite - 2021-09-29 19:00:28