[알고리즘] 힙과 힙정렬(2) - 예제

[문제1] 삽입식 힙 생성 프로그램

- 순차힙으로 구현(배열)

- 최대힙으로 구현(삭제도 최대값 삭제)

- 연산 효율을 위해 배열 인덱스 0 위치는 사용하지않고 비움

- 데이터 구조를 단순하게 하기 위해 힙의 항목(키, 원소)쌍에서 원소를 생략하고 키만 사용

- 키들은 중복이 없는 1이상의 정수

- 최대항목수 < 100

- i <키> : <키>를 힙에 삽입하고 0을 출력

- d : 힙에서 삭제하여 반환된 키를 출력

- p : 힙의 내용을 출력(레벨순서로 출력)

- q : 프로그램 종료

입력예시                  출력예시

i 5  i 15  i 10  i 20  i 30  i 25  p  d  i 31  i 29  d  p  q

0  0  0  0  0  0   30 20 25 5 15 10  30  0  0  31   29 20 25 5 15 10

#include<stdio.h> #include<stdlib.h> int H[100], n = 0; void upHeap(int i) { int temp; if (i == 1) { return; } if (H[i] <= H[i / 2]) { return; } temp = H[i]; H[i] = H[i / 2]; H[i / 2] = temp; upHeap(i / 2); } void insertItem(int key) { H[++n] = key; upHeap(n); } void downHeap(int i) { int bigger, temp; if ((n < (i * 2)) && (n < (i * 2 + 1))) { return; } bigger = i * 2; if (n >= i * 2 + 1) { if (H[i * 2 + 1] > H[bigger]) { bigger = i * 2 + 1; } } if (H[i] >= H[bigger]) { return; } temp = H[i]; H[i] = H[bigger]; H[bigger] = temp; downHeap(bigger); } int removeMax() { int key; key = H[1]; H[1] = H[n--]; downHeap(1); return key; } void printHeap() { for (int i = 1; i < n + 1; i++) { printf(" %d", H[i]); } printf("\n"); } void main(){ char select; int key; while (1) { scanf("%c", &select); if (select == 'i') { scanf("%d", &key); insertItem(key); printf("0\n"); getchar(); } else if (select == 'd') { printf("%d\n", removeMax()); getchar(); } else if(select == 'p') { printHeap(); getchar(); } else if (select == 'q') { break; } } }

[문제2] 상향식 힙 생성 프로그램

- 순차힙으로 구현(배열)

- 최대힙으로 구현(삭제도 최대값 삭제)

- 연산 효율을 위해 배열 인덱스 0 위치는 사용하지않고 비움

- 데이터 구조를 단순하게 하기 위해 힙의 항목(키, 원소)쌍에서 원소를 생략하고 키만 사용

- 키들은 중복이 없는 1이상의 정수

- 최대항목수 < 100

- 첫 번째 라인 : 키 개수

- 두 번째 라인 : 키들

- 출력 : 힙 내용(레벨순서)

입력예시                                   출력예시

8  5 15 10 20 30 25 31 29

31 30 25 29 15 5 10 20

#include<stdio.h> #include<stdlib.h> int H[100], n = 0; void upHeap(int i) { int temp; if (i == 1) { return; } if (H[i] <= H[i / 2]) { return; } temp = H[i]; H[i] = H[i / 2]; H[i / 2] = temp; upHeap(i / 2); } void downHeap(int i) { int bigger, temp; if ((n < (i * 2)) && (n < (i * 2 + 1))) { return; } bigger = i * 2; if (n >= i * 2 + 1) { if (H[i * 2 + 1] > H[bigger]) { bigger = i * 2 + 1; } } if (H[i] >= H[bigger]) { return; } temp = H[i]; H[i] = H[bigger]; H[bigger] = temp; downHeap(bigger); } // 힙생성 - 재귀버전 void rBuildHeap(int i) { if (i > n) { return; } rBuildHeap(2 * i); rBuildHeap(2 * i + 1); downHeap(i); } // 힙생성 - 비재귀버전 void buildHeap() { for (int i = n / 2; i >= 1; i--) { downHeap(i); } } void printHeap() { for (int i = 1; i < n + 1; i++) { printf(" %d", H[i]); } printf("\n"); } void main() { int keyNumber, value, i; scanf("%d", &keyNumber); for (i = 1; i < keyNumber + 1; i++) { scanf("%d", &value); H[i] = value; n++; } rBuildHeap(1); // buildHeap(); printHeap(); }