DEAP(double-ended heap)은 힙(heap) 구조로서 이중 우선 순위 큐(double-ended priority queue)의 일종입니다. 즉, STL에 있는 prority_queue와 비슷한 기능을 합니다. 이 자료구조의 목적은 크기가 서로 다른 여러 자료가 있을 때, 이중 가장 큰 것이나 가장 작은 것을 순서대로 빠르게 가져오는 것입니다. 이를 구현한 자료 구조로 min heap과 max heap이 각 층별로 번갈아가며 있는 Min-max heap도 있으나, 두 heap을 서로 따로 둔다는 아이디어를 가지고 구현한 DEAP이 더 직관적이며 구현하기도 더 재미있습니다.
링크드 리스트, 트리, 해쉬 정도는 MFC에도 구현돼 있을 정도로 친근한 자료 구조이지만, 자료 구조 책의 뒷부분 무렵에 나오는 힙 같은 것은 대개 낯설어 보입니다. 하지만 이것들은 의외로 매우 유용합니다. 자료 삽입, 최대값 얻기, 최소값 얻기 작업을 모두 log n만에 할 수 있습니다. 더구나 값을 얻으면서 이 자료를 삭제하는 데 걸리는 시간이 log n이지 값 자체를 얻는 시간은 상수입니다. 이 n은 자료의 크기가 아니라 힙의 크기이기 때문에, 수십만 개의 자료가 실시간으로 들어오고 있고, 이중에서 가장 중요한 100개의 자료만을 추려낸다고 할 때, 자료를 모두 메모리로 읽어 정렬하지 않고도 100칸의 배열 안에서 이 일을 할 수 있지요.
이 프로그램의 CDeap은 DEAP을 템플릿 클래스로 구현한 것으로, 랭킹 기능에 맞게 만들어져 있습니다. 이미 힙이 꽉 차 있으면 원소를 삽입할 때 어떡할 것인지 policy를 지정할 수 있습니다. 큰 구조체를 대상으로 이 클래스를 쓸 경우, TYPE에는 A를, ARG_TYPE에는 const A &와 같은 자료형을 주면 됩니다.
Deap이 일반 heap과 다른 점은?
deap은 한 배열로 min heap과 max heap을 동시에 표현합니다. 흔히 힙 정렬을 할 때나 일반 힙을 표현할 때, 맨 꼭대기의 인덱스를 0이 아닌 1로 삼는 경우가 있습니다. (배열의 포인터에다 1을 뺌으로써) deap은 꼭대기에 원소가 두 개가 있기 때문에 인덱스를 2부터 시작하게 하는 게 유리합니다. 이렇게 하면 어느 인덱스에서나 그 인덱스 번호에 2를 곱함으로써 아래층 왼쪽의 원소를 가리키게 할 수 있습니다.
즉, 2 [3], 4 5, [6 7], 8 9 10 11 [12 13 14 15], ... 의 순서대로 [ ] 안의 수치는 max heap의 인덱스이고 그렇지 않은 2, 4, 5, 8, ...은 min heap의 인덱스가 되는 것입니다. max heap의 인덱스는 그 수에서 가장 큰 2진법 비트와 그 다음 비트가 언제나 1임을 알 수 있습니다. 3=11, 6=110, 13=1101, 15=1111
deap에 원소가 추가되면 처음에는 새 원소가 일반 heap과 마찬가지로 배열의 가장 마지막 인덱스에 있게 됩니다. 그 인덱스는 min heap 인덱스일 수도 있고 max heap 인덱스일 수도 있습니다.
이제 이 원소와, min이든 max이든 맞은편 heap에서 같은 위치에 있는 원소와 비교를 해야 합니다. 8 ↔ 12, 7 ↔ 5와 같은 식입니다. 만약 정확하게 같은 위치에 있는 인덱스가 존재하지 않는다면 그 인덱스의 부모 인덱스에 있는 원소와 비교하면 됩니다. 가령, 원소가 min heap에 속하는 10번 인덱스와 짝인 max heap의 인덱스는 14인데 원소가 그만치 없어서 이 인덱스가 존재하지 않는다면 부모인 7번 인덱스가 짝이 되는 것입니다.
그래서 새 원소가 min heap에 추가됐는데 max heap의 짝이 새 원소보다 값이 작은 경우, 또는 반대로 새 원소가 max heap에 추가됐는데 min heap의 짝이 새 원소보다 큰 경우 원소의 위치를 뒤바꿉니다. 그러고 나서 새 위치를 기준으로 새로운 원소가 min heap에 속한다면 min heap대로, 혹은 max heap에 속한다면 max heap대로 해당 힙의 정의에 맞게 새 원소와 부모 원소를 재배치하면 삽입 작업이 끝납니다.
한편 삭제는 min 또는 max 원소를 대상으로 할 수 있는데, 해당 힙의 맨 꼭대기 원소를 제거한 후 아래의 원소들 중 그 힙의 조건에 맞는 원소를 하나씩 끌어올려 줍니다. 그러면 맨 마지막 빈 자리가 남게 되죠. 거기에다가 배열상으로 제일 마지막 인덱스에 해당하는 원소를 삽입해서 위에서 열거한 삽입 작업(자기 짝과 위치 교환 등)을 다시 시행해 주면 됩니다.
이 프로그램은 CDeap 클래스를 이용해 허프만 코딩도 구현하여 시연했습니다. 허프만 코딩은 자주 쓰이는 정보에 더 짧은 코드를 할당하고, 드물게 나타나는 정보에 드는 코드를 늘임으로써 전체적으로 데이터의 크기를 줄이는 기본적인 압축 기법입니다. A부터 Z까지의 출현 빈도가 들어왔을 때, 각 빈도수에 맞는 허프만 트리를 생성하고, 그 트리대로 코드를 출력해 주는 예가 나옵니다. 모든 글자를 일괄적으로 5비트 코드로 정하는 것보다 허프만 트리를 쓰면 전체 코드 크기가 얼마나 줄어드나 확인할 수 있습니다.
하지만 허프만 코딩을 할 때는 heap으로부터 가장 작은 값을 얻어오고 힙에서 이것을 빼내는 동작밖에 하지 않기 때문에, 굳이 양방향 힙이 아니더라도 Min-heap만 구현한 클래스로도 이 코드를 실행할 수 있습니다.
Sorting with Deap: Original order: 108 9 51 83 170 33 66 5 82 104 8 43 151 25 118 52 36 17 148 85 81 183 133 154 185 72 171 46 73 125 161 111 128 130 114 117 131 24 141 68 48 188 155 76 99 7 2 39 60 13 30 140 94 11 152 107 169 179 195 150 65 164 21 64 42 123 145 93 95 159 22 14 47 139 106 75 55 194 136 180 20 84 182 160 100 26 166 102 1 78 62 89 16 172 177 121 19 135 167 110 168 147 137 54 124 41 162 71 96 173 158 44 197 101 127 174 70 87 191 90 40 67 35 105 184 193 92 12 113 29 181 126 23 109 199 132 28 59 149 34 61 80 189 91 56 50 142 32 116 134 Heap form: 1 | 199 | 5 2 | 197 195 | 8 11 20 7 | 194 189 188 193 | 9 13 14 17 44 26 25 16 | 177 181 183 173 182 180 185 191 | 12 19 28 34 22 32 71 24 46 68 82 48 81 40 35 33 | 133 161 168 167 140 142 154 162 158 179 174 170 166 150 105 184 | 21 29 39 23 118 59 52 61 43 30 41 47 94 72 36 55 141 136 104 84 127 160 70 85 151 90 73 67 62 89 83 125 | 108 121 135 123 159 110 149 147 137 56 139 134 106 75 96 131 152 148 107 101 169 171 100 87 155 102 76 78 65 99 164 172 | 92 66 113 64 42 126 111 109 130 132 93 60 145 95 128 80 51 91 54 50 124 114 116 117 Min form: 1 2 5 7 8 9 11 12 13 14 16 17 19 20 21 22 23 24 25 26 28 29 30 32 33 34 35 36 39 40 41 42 43 44 46 47 48 50 51 52 54 55 56 59 60 61 62 64 65 66 67 68 70 71 72 73 75 76 78 80 81 82 83 84 85 87 89 90 91 92 93 94 95 96 99 100 101 102 104 105 106 107 108 109 110 111 113 114 116 117 118 121 123 124 125 126 127 128 130 131 132 133 134 135 136 137 139 140 141 142 145 147 148 149 150 151 152 154 155 158 159 160 161 162 164 166 167 168 169 170 171 172 173 174 177 179 180 181 182 183 184 185 188 189 191 193 194 195 197 199 Max form: 199 197 195 194 193 191 189 188 185 184 183 182 181 180 179 177 174 173 172 171 170 169 168 167 166 164 162 161 160 159 158 155 154 152 151 150 149 148 147 145 142 141 140 139 137 136 135 134 133 132 131 130 128 127 126 125 124 123 121 118 117 116 114 113 111 110 109 108 107 106 105 104 102 101 100 99 96 95 94 93 92 91 90 89 87 85 84 83 82 81 80 78 76 75 73 72 71 70 68 67 66 65 64 62 61 60 59 56 55 54 52 51 50 48 47 46 44 43 42 41 40 39 36 35 34 33 32 30 29 28 25 26 24 23 22 21 20 19 17 16 14 13 12 11 9 8 7 2 5 1 Huffman tree: A's code size is 4 - 1011 B's code size is 6 - 110001 C's code size is 5 - 10101 D's code size is 5 - 11011 E's code size is 3 - 011 F's code size is 6 - 110000 G's code size is 5 - 10100 H's code size is 6 - 111100 I's code size is 4 - 1110 J's code size is 9 - 111111001 K's code size is 6 - 111110 L's code size is 4 - 1001 M's code size is 5 - 00011 N's code size is 4 - 0100 O's code size is 4 - 0101 P's code size is 5 - 00010 Q's code size is 9 - 111111000 R's code size is 4 - 0000 S's code size is 3 - 001 T's code size is 4 - 1000 U's code size is 5 - 11001 V's code size is 7 - 1111111 W's code size is 7 - 1111011 X's code size is 8 - 11111101 Y's code size is 5 - 11010 Z's code size is 7 - 1111010 Compression size 95385 UnCompression size 110310