C언어의 구조체를 이용해서 우선순위 큐를 만들었습니다.
구조체는 아래처럼 정의했습니다.
1 2 3 4 5 6 7 8 9 | typedef struct priority_queue { int heap[MAX_SIZE]; int size; priority_queue(); void swap(int *a, int *b); int push(int value); int pop(); int empty(); } | cs |
데이터를 저장할 heap과
heap의 사이즈를 나타낼 변수
그리고 데이터 swap함수
우선순위큐 push, pop, empty
입니다.
최대 힙으로 구현했고, 최소 힙은 부등호만 바꿔주면 됩니다.
양수에 대해서만 작동하는 힙입니다. 이유는 pop할 때 size == 0이면 -1을 리턴하게 했기 때문입니다.
input)
2
10
10 49 38 17 56 92 8 1 13 55
13
4 22 50 13 5 1 22 35 21 7 99 100 14
출력결과)
2
10
10 49 38 17 56 92 8 1 13 55
#1
92 56 55 49 38 17 13 10 8 1
13
4 22 50 13 5 1 22 35 21 7 99 100 14
#2
100 99 50 35 22 22 21 14 13 7 5 4 1
궁금한 것은 댓글 주세요
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 | #include <stdio.h> #define MAX_SIZE 100 typedef struct priority_queue { int heap[MAX_SIZE]; int size; priority_queue() { size = 0; } void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } int push(int value) { if (size + 1 > MAX_SIZE) { return 0; } heap[size] = value; int current = size; int parent = (size - 1) / 2; while (current > 0 && heap[current] > heap[parent]) { swap(&heap[current], &heap[parent]); current = parent; parent = (parent - 1) / 2; } size++; return 1; } int pop() { if (size <= 0) return -1; int ret = heap[0]; size--; heap[0] = heap[size]; int current = 0; int leftChild = current * 2 + 1; int rightChild = current * 2 + 2; int maxNode = current; while (leftChild < size) { if (heap[maxNode] < heap[leftChild]) { maxNode = leftChild; } if (rightChild < size && heap[maxNode] < heap[rightChild]) { maxNode = rightChild; } if (maxNode == current) { break; } else { swap(&heap[current], &heap[maxNode]); current = maxNode; leftChild = current * 2 + 1; rightChild = current * 2 + 2; } } return ret; } int empty() { if (size == 0) { return 1; } else { return 0; } } }priority_queue; int main(int argc, char* argv[]) { int T, N; scanf("%d", &T); for (int test_case = 1; test_case <= T; test_case++) { scanf("%d", &N); priority_queue pq; for (int i = 0; i < N; i++) { int value; scanf("%d", &value); pq.push(value); } printf("#%d\n", test_case); while(!pq.empty()) printf("%d ", pq.pop()); printf("\n"); } return 0; } | cs |
'CS기본지식 > 자료구조' 카테고리의 다른 글
[1918] 후위표기식 (0) | 2017.11.27 |
---|---|
[C언어] 원형 큐(라운드 큐) (0) | 2017.09.07 |
[2263] 트리의 순회 (1) | 2017.08.27 |
스택 계산기 (0) | 2017.06.13 |
[1918] 후위표기식 (2) | 2017.06.13 |