Sep 19, 2019 โ€ข4 min read โ˜•

๐Ÿ’ป Heap Sort, ํž™ ์ •๋ ฌ์ด๋ž€?

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)
ยฉ 2021 Dojin Kim, Built with Gatsby