×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,191,305명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형


힙에 대한 설명은 아래에서 참고한다.

https://www.crocus.co.kr/1184?category=150836


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
 
#include <iostream>
#define MAX 101
#define SWAP(a,b){int t = a; a = b; b = t;}
 
 // 최소 힙
int heap[MAX];
int hCnt;
 
void print() {
    printf("heap :: [ ");
    for (int i = 1; i <= hCnt; i++)
        printf("%d ",heap[i]);
    printf("]\n");
}
 
void push(int val) {
    heap[++hCnt] = val;
 
    int cur = hCnt;
    int par = cur / 2;
    while (cur > && heap[cur] < heap[par]) {
        SWAP(heap[cur], heap[par]);
        cur = par;
        par = cur / 2;
    }
}
 
int pop() {
    if (hCnt == 0)
        return -1;
 
    int val = heap[1];
    heap[1= heap[hCnt--];
 
    int cur = 1;
    int next;
 
    while (1) {
        next = cur * 2;
        if (next < hCnt && heap[next] > heap[next + 1]) // 무조건 right가 존재한다.(hCnt까지 힙이 존재하니)
            next++// 오른쪽 노드가 더 작으면 next를 오른쪽으로 만들어준다.
        if (next > hCnt || heap[cur] < heap[next])
            break// 부모가 자식보다 작은값이면 break(최소 힙 유지)
        SWAP(heap[cur], heap[next]);
 
        cur = next;
    }
 
    return val;
}
 
int main() {
    print();
    push(5);
    print();
    push(2);
    print();
    push(2);
    print();
    push(1);
    print();
    printf("팝 :: %d\n", pop());
    print();
    printf("팝 :: %d\n", pop());
    print();
    printf("팝 :: %d\n", pop());
    print();
    printf("팝 :: %d\n", pop());
    print();
    printf("팝 :: %d\n", pop());
    print();
    return 0;
}
 
cs






반응형