Heap Sort(ํ์ ๋ ฌ)๋ Complete Binary Tree(์์ ์ด์ง ํธ๋ฆฌ)
ํ์์ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ฌ์ฉํด์ ์ ๋ ฌ์ ํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ์์ ์ด์ง ํธ๋ฆฌ๋ ๊ฐ level๋ง๋ค ์ผ์ชฝ๋ถํฐ ์ฑ์๋ฃ์ ํธ๋ฆฌ์ ๊ตฌ์กฐ๋ฅผ ์๋ฏธํ๋ค. Binary Heap์ parent ๋
ธ๋๊ฐ ๋๊ฐ์ child ๋
ธ๋๋ณด๋ค ํฌ๊ฒ ๋ง๋ค์๋ ์๊ณ ์๊ฒ ๋ง๋ค์๋ ์๋ค. ์ ์๋ max heap
์ด๋ผ๊ณ ๋ถ๋ฅด๊ณ , ํ์๋ min heap
์ด๋ผ๊ณ ๋ถ๋ฅธ๋ค. ์ด Heap์ binary tree๋ก ๋ํ๋ผ ์ ์์ง๋ง, ์ผ๋ฐ array๋ก๋ ๋ํ๋ผ ์ ์๋ค.
์ด๋ป๊ฒ Binary Heap์ array๋ก ๋ํ๋ด๋๊ฐ?
Binary Heap์ด ์์ ์ด์ง ํธ๋ฆฌ์ด๊ธฐ ๋๋ฌธ์ array๋ก ๋ํ๋ผ ์ ์๋ ๊ฒ์ด๋ค. Parent ๋ ธ๋๊ฐ l ์ธ๋ฑ์ค์ ์๋ค๊ณ ๊ฐ์ ํด๋ณด์. ๊ทธ๋ ๋ค๋ฉด ์ผ์ชฝ์ ์์ ๋ ธ๋์ index๋ 2 * l + 1 ๋ก ์์๋ผ ์ ์๊ณ ์ค๋ฅธ์ชฝ ์์ ๋ ธ๋๋ 2 * l + 2๋ก ์์๋ผ ์ ์๋ค. ์์ ๋ ธ๋๋ค์ ๋ฐ๋๋ก ๊ณ์ฐํด์ parent ๋ ธ๋์ index๋ฅผ ์์๋ผ ์ ์๋ค.
์ด๋ ๊ฒ array๋ฅผ ์ด์ง ํธ๋ฆฌ์ฒ๋ผ ์ฐ์์ ํด์ ํ ์ ์๋ค.
Pseudo-code ์ค๋ช
Pseudo-code๋ฅผ ํ๋์ฉ ๋ณด๊ธฐ ์ ์ ์๊ณ ๋ฆฌ์ฆ์ ๊ธฐ๋ณธ ์๋๋ฒ์ ์์๋ณด๋ ค๊ณ ํ๋ค.
์์ ์ซ์ โ ํฐ ์ซ์๋ก ์ ๋ ฌํ๋ ค๋ฉด, max heap
์ ์ฌ์ฉํด์ผ ํ๋ค. max heap
์ด๊ธฐ ๋๋ฌธ์ ๊ฐ์ฅ ํฐ ์ซ์๊ฐ root์ ์์นํด ์๋ค. ์ด root๋ฅผ ๊ฐ์ฅ ๋ง์ง๋ง ๋
ธ๋์ swap์ ํ๊ณ array์ ์ฌ์ด์ฆ๋ฅผ ํ๋ ์ค์ธ๋ค. ์ด๋ ๊ฒ ๋๋ฉด ๊ฐ์ฅ ํฐ ์ซ์ ์์ผ๋ก array ๋งจ ๋ค์ ์์นํ๊ฒ ๋๋ ๊ฒ์ด๋ค. Swap์ ํ๊ณ ๋์ heapify
๋ผ๋ ๋ฉ์ปค๋์ฆ์ ์ฌ์ฉํด์ ๋จ์์๋ ์ซ์๋ค ์ค ๊ฐ์ฅ ํฐ ์๋ฅผ root๋ก ์ด๋์ํจ๋ค. ์ด ๋์์ ๋ฐ๋ณตํ๋ฉด sorting์ด ๋๋ ๊ฒ์ด๋ค.
์ด์ pseudo-code๋ฅผ ํ๋์ฉ ๋ค์ฌ๋ค ๋ณด์.
- line 2: BUILD-MAX-HEAP(line 7~10)์ด๋ผ๋ ํจ์๋ฅผ ํธ์ถํ๋๋ฐ, ์ด ํจ์๋ ์ฃผ์ด์ง array๋ฅผ heapifyํด์
max heap
์ ์ด๋ฃฐ ์ ์๋๋ก ํ๋ ์์ ์ด๋ค. (parent ๋ ธ๋๊ฐ ์์ ๋ ธ๋๋ค๋ณด๋ค ํฐ ํธ๋ฆฌ) -
line 3: for loop
- line 4: root์ธ ์ซ์์ array ๊ฐ์ฅ ๋ง์ง๋ง ์ซ์์ swapํ๋ค.
- line 5: heapSize๋ฅผ ํ๋ ์ค์ฌ์, ์ ๋ ฌ๋ ์ซ์๋ ์ดํ์ heapify ๊ณผ์ ์ ์ ๊ฑฐ์น๊ฒ ํ๋ค.
- line 6: heapify๋ฅผ ํ๋ MAX-HEAPIFY ํจ์๋ฅผ ํธ์ถํ๋ค. ์ด ํจ์๋ recursion์ผ๋ก ์๋ํ๋ค.
- line 12~13: ์์ ๋ ธ๋๋ค์ index๋ฅผ ๊ฐ๊ฐ L,R ๋ณ์์ ์ ์ฅํ๋ค.
-
line 14: ๋ง์ฝ ์ผ์ชฝ ๋ ธ๋๊ฐ heapSize๋ณด๋ค ์๊ณ , ๊ทธ ๊ฐ์ด ์ฃผ์ด์ง ๋ ธ๋์ ๊ฐ๋ณด๋ค ํฌ๋ฉด
- line 15: L์ด ๊ฐ์ฅ ํฐ ์ซ์์ index์ธ ๊ฒ์ผ๋ก ๊ฐ์ฃผํ๋ค
- line 16~17: ๋ง์ฝ ์๋๋ผ๋ฉด, ํ์ฌ ์ฃผ์ด์ง ๋ ธ๋๊ฐ ๊ฐ์ฅ ํฐ ์ซ์์ index์ธ ๊ฒ์ผ๋ก ๊ฐ์ฃผํ๋ค.
-
line 18: L๊ณผ i๋ฅผ ๋น๊ตํด์ ์ด๋ค๊ฒ ๋ ํฐ ์ซ์๋ฅผ ๊ฐ์ง index์ธ์ง ํ์ธ์ ํ์ผ๋ ์ค๋ฅธ์ชฝ ๋ ธ๋์ ๋น๊ต๋ฅผ ํ๋ค.
- line 19: ์ค๋ฅธ์ชฝ ๋ ธ๋๊ฐ L, i ๋ณด๋ค ํฐ ์ซ์๋ฅผ ๊ฐ์ง๊ณ ์์ผ๋ฉด R์ ๊ฐ์ฅ ํฐ ์ซ์์ index๋ก ๊ฐ์ฃผํ๋ค.
-
line 20: ๋ง์ฝ ๊ฐ์ฅ ํฐ ๊ฐ์ index๊ฐ i๊ฐ ์๋๋ผ๋ฉด,
- line 21: i ์๋ฆฌ์ ์๋ ์ซ์์ ๊ฐ์ฅ ํฐ ๊ฐ์ index ์๋ฆฌ์ ์๋ ์ซ์๋ฅผ swapํ๋ค.
- line 22: MAX-HEAPIFY๋ฅผ ๋ค์ ์งํํ๋, largest๋ก heapify๋ฅผ ์์ํ๋ค.
Time Complexity & inplace, stable ์ฌ๋ถ
Heap sort๋ ์ถ๊ฐ์ ์ธ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ฌ์ฉํ์ง ์๊ณ ํ๋์ array๋ก sorting์ ํ๊ธฐ ๋๋ฌธ์ in-place
์๊ณ ๋ฆฌ์ฆ์ด๋ค. ๋ฐ๋ฉด์, unstable
ํ๋ค.
์๊ฐ๋ณต์ก๋๋ O(nlgn)
์ด๋ค. Heapifyํ๋ ๊ณผ์ ์ tree์ ๋์ด๋งํผ ํ๊ธฐ ๋๋ฌธ์ O(lgn)
์ด๋ค. ์ฒ์์ heap์ ๋ง๋๋ ๊ณผ์ ์ array์ ๊ธธ์ด๋งํผ ์ด๋ค์ง๊ธฐ ๋๋ฌธ์ O(n)
์ด๋ค. ์ด ๋์ ํฉํด์ O(nlgn)
์ด ๋์ค๋ ๊ฒ์ด๋ค.
๊ทธ๋ฆผ์ ๋ณด๋ฉด์ Heap sort ์งํ๊ณผ์ ์ ํ๋์ฉ ์ดํด๋ณด๋ ค๊ณ ํ๋ค. ๋จธ๋ฆฌ์์ผ๋ก ์งํ๊ณผ์ ์ ๊ทธ๋ฆฌ๋ฉด์ ๋ณด๋ฉด ์ดํด๊ฐ ์ด๋์ ๋ ๊ฐ ๊ฒ์ ๋๋ค.
a. a์์ ์ด๋ฏธ ์ฒซ heapify๊ณผ์ ์ ๋ง์น ์ํ์ด๋ค.
b. root์ ๊ฐ์ฅ ๋ง์ง๋ง ๋ ธ๋๋ฅผ swapํ๊ณ heapSize -= 1์ ํ๋ค. ๊ทธ๋ฆฌ๊ณ root๊ฐ 1์ธ๋ฐ ์์ ๋ ธ๋๋ค๋ณด๋ค ์๊ธฐ ๋๋ฌธ์ heapify๊ณผ์ ์ ๊ฑฐ์น๋ค.
- 1์ 14์ 10์ค ๋ ํฐ ์ซ์์ธ 14์ swap๋์ ์ผ์ชฝ ์์ ๋ ธ๋๋ก ์ด๋ํ๋ค.
- ๋ค์ 1์ ์์ ๋ ธ๋๋ฅผ ๋ดค๋๋ 8๊ณผ 7์ด ์๊ณ ๊ทธ ์ค ๋ ํฐ ์ซ์์ธ 8๊ณผ swap๋๊ณ ๋ค์ ์ผ์ชฝ ์์ ๋ ธ๋๋ก ์ด๋ํ๋ค.
- 1์ ์์ ๋ ธ๋๋ 2์ 4๊ธฐ์, 4์ swap๋์ ์ค๋ฅธ์ชฝ ์์ ๋ ธ๋๋ก ์ด๋ํ๋ค. ๊ทธ๋ ๊ฒ ํด์ ๋ง๋ค์ด์ง ํธ๋ฆฌ์ ๋ชจ์์ด (b)์ ๊ทธ๋ฆผ์ด๋ค.
c. root์ธ 14์ ๊ฐ์ฅ ๋ง์ง๋ง ๋ ธ๋์ธ 1๊ณผ swapํ๊ณ heapSize -= 1์ ํ๋ค. ๋ค์ heapify๊ณผ์ ์ ๊ฑฐ์น๋ค.
- 8๊ณผ 10์ค 10์ด ๋ ํฌ๊ธฐ์ 10๊ณผ 1์ด swap๋๊ณ , 1์ ์ค๋ฅธ์ชฝ ๋ ธ๋๋ก ์ด๋ํ๋ค.
- ์์ ๋ ธ๋๋ค์ด 9์ 3์ด๊ธฐ์, 9์ swap๋์ 1์ ์ผ์ชฝ ๋ ธ๋๋ก ์ด๋ํ๋ค. ๊ทธ๋ ๊ฒ ํด์ ๋ง๋ค์ด์งใด ํธ๋ฆฌ์ ๋ชจ์์ด (c)์ ๊ทธ๋ฆผ์ด๋ค.
...
์ด๋ ๊ฒ ์ญ ์งํํ๋ฉด sorting๋ array๋ฅผ ์ป์ ์ ์๊ฒ ๋๋ค.
Python Code
import random
class HeapSort:
def __init__(self, num, heapSize):
self.num = num
self.heapSize = heapSize
def heap_sort(self):
# ๊ธธ์ด๋ถํฐ 0๋ฒ์งธ๊น์ง max_heapify๋ฅผ ํด์ผ ํ๋ค.
for i in range(len(self.num), -1, -1):
self.max_heapify(i)
# root์ ๊ฐ์ฅ ํฐ ์๋ฅผ ๋จ์ผ๋, ๋ง์ง๋ง ์์๊ณผ ๋ฐ๊พธ๊ณ ๋ค์ heapify๋ฅผ ์งํํ๋ค
for i in range(len(self.num)-1, 0, -1):
self.num[0], self.num[i] = self.num[i], self.num[0]
self.heapSize -= 1
self.max_heapify(0)
def max_heapify(self, i):
largest = i
L = 2 * i + 1
R = 2 * i + 2
# ์ผ์ชฝ ์์์ด ํ์ฌ ๋
ธ๋์ ๊ฐ๋ณด๋ค ํฐ์ง ํ์ธํ๋ค
if (L < self.heapSize) and (self.num[L] > self.num[i]):
largest = L
else:
largest = i
# ์ค๋ฅธ์ชฝ ์์์ด ์ผ์ชฝ ์์, ํ์ฌ ๋
ธ๋๋ณด๋ค ํฐ์ง ํ์ธํ๋ค
if (R < self.heapSize) and (self.num[R] > self.num[largest]):
largest = R
# ์์ ์ค ํ๋๊ฐ ํ์ฌ ๋
ธ๋๋ณด๋ค ํฌ๋ฉด ๋ฐ๊พธ๊ณ , heapify๋ฅผ ๋ค์ ํ๋ค
if largest != i:
self.num[i], self.num[largest] = self.num[largest], self.num[i]
self.max_heapify(largest)
number = [i for i in range(10)]
random.shuffle(number)
print(number)
heap = HeapSort(number, len(number))
heap.heap_sort()
print(heap.num)