tony9402

[SCCC 스터디] 힙 정렬 직접 구현 본문

알고리즘/공부

[SCCC 스터디] 힙 정렬 직접 구현

ssu_gongdoli 2019. 1. 14. 01:14
반응형


3일차에서 최소 힙을 짰었는데 너무 드럽게 짜서 다시 간단하게 짜봤다.

또한 최소 힙을 짜면서 최대 힙도 다시 짜봤다.


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
#include<iostream>
#include<algorithm>
 
using namespace std;
 
int heap[200000];
int Size = 1;
 
void push(int data)
{
    heap[++Size] = data;
    int idx = Size;
    while (idx > 1)
    {
        if (heap[idx] > heap[idx / 2])
        {
            swap(heap[idx], heap[idx / 2]);
        }
        idx /= 2;
    }
}
 
int pop()
{
    if (Size == 1)return 0;
    int top = heap[1];
    heap[1] = heap[Size];
    heap[Size--] = 0;
    int idx = 1;
    while (1)
    {
        if (heap[idx] < heap[idx * 2] || heap[idx] < heap[idx * 2 + 1])
        {
            if (heap[idx * 2] > heap[idx * 2 + 1])
            {
                swap(heap[idx * 2], heap[idx]);
                idx = idx * 2;
            }
            else
            {
                swap(heap[idx * 2 + 1], heap[idx]);
                idx = idx * 2 + 1;
            }
        }
        else
        {
            break;
        }
    }
    return top;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int input;
    while (n--)
    {
        cin >> input;
        if (!input)
        {
            cout << pop() << '\n';
        }
        else
        {
            push(input);
        }
    }
    return 0;
}

cs




2.  최소 힙


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
#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std;
 
int heap[200000];
int Size = 0;
 
void push(int data)
{
    heap[++Size] = data;
    int idx = Size;
    while (idx > 1)
    {
        if (heap[idx] < heap[idx / 2])
        {
            swap(heap[idx], heap[idx / 2]);
            idx /= 2;
        }
        else break;
    }
}
 
int pop()
{
    if (!Size)return 0;
    int top = heap[1];
    heap[1] = heap[Size];
    heap[Size--] = -1;
    int idx = 1;
 
    while (1)
    {
        bool left = heap[idx * 2] > 0;
        bool right = heap[idx * 2 + 1] > 0;
 
        if ((left && heap[idx * 2] < heap[idx]) || (right && heap[idx * 2 + 1] < heap[idx]))
        {
            if (right && left)
            {
                if (heap[idx * 2] > heap[idx * 2 + 1])
                {
                    swap(heap[idx], heap[idx * 2 + 1]);
                    idx = idx * 2 + 1;
                }
                else
                {
                    swap(heap[idx], heap[idx * 2]);
                    idx = idx * 2;
                }
            }
            else if (right)
            {
                swap(heap[idx], heap[idx * 2 + 1]);
                idx = idx * 2 + 1;
            }
            else if (left)
            {
                swap(heap[idx], heap[idx * 2]);
                idx = idx * 2;
            }
        }
        else break;
    }
    return top;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    while (n--)
    {
        int input;
        cin >> input;
        if (input) push(input);
        else cout << pop() << '\n';
    }
}
cs


반응형
저작자표시 비영리 동일조건

'알고리즘 > 공부' 카테고리의 다른 글

[영상처리 스터디] Queue C로 구현하기  (2) 2019.01.14
[SCCC 스터디] 선택, 퀵, 머지, 카운팅 소트  (0) 2019.01.14
[SCCC 스터디] 3일차 정렬  (0) 2019.01.13
[SCCC 스터디] 2 일차 구현+시간복잡도  (0) 2019.01.13
[SCCC 스터디] 1 일차 STL  (0) 2019.01.11
'알고리즘/공부' Related Articles more
Comments