YS's develop story

Heap (ํž™) ์ •๋ฆฌ ๋ณธ๋ฌธ

Data Structure

Heap (ํž™) ์ •๋ฆฌ

Yusang 2021. 7. 28. 09:37

๐Ÿ‘จ๐Ÿผ‍๐Ÿ’ป Heap (ํž™) ์ •๋ฆฌ With Python

๐Ÿฅ Heap ์ด๋ž€?

๋ฐ์ดํ„ฐ์—์„œ ์ตœ๋Œ“๊ฐ’๊ณผ ์ตœ์†Ÿ๊ฐ’์„ ๋น ๋ฅด๊ฒŒ ์ฐพ๊ธฐ ์œ„ํ•ด ๊ณ ์•ˆ๋œ ์™„์ „ ์ด์ง„ํŠธ๋ฆฌ(Complete Binary Tree)์ž…๋‹ˆ๋‹ค.

 

์™„์ „ ์ด์ง„ํŠธ๋ฆฌ?

  • Node๋ฅผ ์‚ฝ์ž…ํ•  ๋•Œ ์ตœํ•˜๋‹จ ์™ผ์ชฝ Node๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ์‚ฝ์ž…ํ•˜๋Š” Tree

 

๋ฐฐ์—ด์— ๋ฐ์ดํ„ฐ๋ฅผ ๋„ฃ๊ณ , ์ตœ๋Œ“๊ฐ’๊ณผ ์ตœ์†Ÿ๊ฐ’์„ ์ฐพ์œผ๋ ค๋ฉด O(n) ์ด ๊ฑธ๋ฆฌ์ง€๋งŒ

ํž™์— ๋ฐ์ดํ„ฐ๋ฅผ ๋„ฃ๊ณ , ์ตœ๋Œ“๊ฐ’๊ณผ ์ตœ์†Ÿ๊ฐ’์„ ์ฐพ์œผ๋ฉด O(logn) ์ด ๊ฑธ๋ฆฌ๊ธฐ ๋•Œ๋ฌธ์—

์ตœ๋Œ“๊ฐ’, ์ตœ์†Ÿ๊ฐ’์„ ๋น ๋ฅด๊ฒŒ ์ฐพ์•„์•ผ ํ•˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ ๋ฐ ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ํ™œ์šฉ๋ฉ๋‹ˆ๋‹ค.

 

ํž™์€ ์•„๋ž˜์˜ ๋‘ ๊ฐ€์ง€ ์กฐ๊ฑด์„ ๊ฐ€์ง€๊ณ  ์žˆ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

  1. ๊ฐ ๋…ธ๋“œ์˜ ๊ฐ’์€ ํ•ด๋‹น ๋…ธ๋“œ์˜ ์ž์‹ ๋…ธ๋“œ๊ฐ€ ๊ฐ€์ง„ ๊ฐ’๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™์Šต๋‹ˆ๋‹ค. 
  2. ์™„์ „ ์ด์ง„ํŠธ๋ฆฌ ํ˜•ํƒœ๋ฅผ ๊ฐ€์ง‘๋‹ˆ๋‹ค.

 

๐Ÿ‹ Heap VS Binary Search Tree

๊ณตํ†ต์ 

  • ํž™๊ณผ ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ๋Š” ๋ชจ๋‘ ์ด์ง„ํŠธ๋ฆฌ์ž…๋‹ˆ๋‹ค.

์ฐจ์ด์ 

  • ํž™์€ ๊ฐ ๋…ธ๋“œ์˜ ๊ฐ’์ด ์ž์‹ ๋…ธ๋“œ๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™์Šต๋‹ˆ๋‹ค.
  • ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ๋Š” ์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ์˜ ๊ฐ’์ด ๊ฐ€์žฅ ์ž‘๊ณ , ๊ทธ๋‹ค์Œ ๋ถ€๋ชจ ๋…ธ๋“œ, ๊ทธ๋‹ค์Œ ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ ๊ฐ’์ด ๊ฐ€์žฅ ํฝ๋‹ˆ๋‹ค.
  • ํž™์€ ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์˜ ์กฐ๊ฑด์ธ ์ž์‹ ๋…ธ๋“œ์—์„œ ์ž‘์€ ๊ฐ’์€ ์™ผ์ชฝ, ํฐ ๊ฐ’์€ ์˜ค๋ฅธ์ชฝ์ด๋ผ๋Š” ์กฐ๊ฑด์ด ์—†์Šต๋‹ˆ๋‹ค.
  • ํž™์˜ ์™ผ์ชฝ ๋ฐ ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ์˜ ๊ฐ’์€ ์˜ค๋ฅธ์ชฝ์ด ํด ์ˆ˜๋„ ์žˆ๊ณ , ์™ผ์ชฝ์ด ํด ์ˆ˜๋„ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ๋Š” ํƒ์ƒ‰์„ ์œ„ํ•œ ๊ตฌ์กฐ, ํž™์€ ์ตœ๋Œ€/์ตœ์†Ÿ๊ฐ’ ๊ฒ€์ƒ‰์„ ์œ„ํ•œ ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค.

 

๐ŸŠ Heap์— ๋ฐ์ดํ„ฐ ๋„ฃ๊ธฐ

Heap์€ ์™„์ „ ์ด์ง„ํŠธ๋ฆฌ์ด๊ธฐ ๋•Œ๋ฌธ์— ์‚ฝ์ž…ํ•  Node๋Š” ์™ผ์ชฝ ์ตœํ•˜๋‹จ Node๋ถ€ํ„ฐ ์ฑ„์›Œ์ง‘๋‹ˆ๋‹ค.

 

 

์ฑ„์›Œ์ง„ ๋…ธ๋“œ ์œ„์น˜์—์„œ, ๋ถ€๋ชจ ๋…ธ๋“œ๋ณด๋‹ค ๊ฐ’์ด ํด ๊ฒฝ์šฐ, ๋ถ€๋ชจ ๋…ธ๋“œ์™€ ์œ„์น˜๋ฅผ ๋ฐ”๊ฟ”์ฃผ๋Š” ์ž‘์—…์„ ๋ฐ˜๋ณตํ•˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

 

๐Ÿ‰ Heap์˜ ๋ฐ์ดํ„ฐ ์‚ญ์ œํ•˜๊ธฐ

Heap์—์„œ ๋ฐ์ดํ„ฐ๋ฅผ ๊บผ๋‚ผ ๊ฒฝ์šฐ ์ตœ์ƒ๋‹จ Node๋ฅผ ๊บผ๋‚ด๋Š” ๊ฒƒ์ด ์ผ๋ฐ˜์ ์ž…๋‹ˆ๋‹ค.

(Heap์˜ ๋ชฉ์ ์ธ ์ตœ์†Ÿ๊ฐ’, ์ตœ๋Œ“๊ฐ’์„ ์•Œ์•„๋‚ด๊ธฐ ์œ„ํ•ด์„œ...)

 

์ตœ์ƒ๋‹จ Node๋ฅผ ์‚ญ์ œ ์‹œ,

๋งจ ๋งˆ์ง€๋ง‰์— ์ž…๋ ฅ๋œ Node๊ฐ€ ์ตœ์ƒ๋‹จ Node๋กœ ์ด๋™ํ•˜์—ฌ ์˜ฌ๋ฐ”๋ฅธ ์œ„์น˜๋ฅผ ์ฐพ์„ ๋•Œ๊นŒ์ง€ 

Node์˜ ์œ„์น˜๋ฅผ ๋ฐ”๊ฟ”์ฃผ๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

 

๐Ÿˆ Heap ๊ตฌํ˜„ With Python

 

ํž™ ๊ตฌํ˜„ ์‹œ ๋ฐฐ์—ด ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ํ™œ์šฉํ•ฉ๋‹ˆ๋‹ค.

๊ทœ์น™์„ ํ†ตํ•ด์„œ heap์„ ๋ฐฐ์—ด๋กœ ์ €์žฅํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

  • ๋ถ€๋ชจ ๋…ธ๋“œ ์ธ๋ฑ์Šค ๋ฒˆํ˜ธ =  ์ž์‹ ๋…ธ๋“œ ์ธ๋ฑ์Šค ๋ฒˆํ˜ธ // 2
  • ์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ ์ธ๋ฑ์Šค ๋ฒˆํ˜ธ = ๋ถ€๋ชจ ๋…ธ๋“œ ์ธ๋ฑ์Šค ๋ฒˆํ˜ธ * 2
  • ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ ์ธ๋ฑ์Šค ๋ฒˆํ˜ธ = ๋ถ€๋ชจ ๋…ธ๋“œ ์ธ๋ฑ์Šค ๋ฒˆํ˜ธ * 2 + 1

 

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)
    
    def move_down(self, popped_idx):
        left_child_popped_idx = popped_idx * 2
        right_child_popped_idx = popped_idx * 2 + 1
        
        # case1: ์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ๋„ ์—†์„ ๋•Œ
        if left_child_popped_idx >= len(self.heap_array):
            return False
        # case2: ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ๋งŒ ์—†์„ ๋•Œ
        elif right_child_popped_idx >= len(self.heap_array):
            if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                return True
            else:
                return False
        # case3: ์™ผ์ชฝ, ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ ๋ชจ๋‘ ์žˆ์„ ๋•Œ
        else:
            if self.heap_array[left_child_popped_idx] > self.heap_array[right_child_popped_idx]:
                if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                    return True
                else:
                    return False
            else:
                if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
                    return True
                else:
                    return False
    
    def pop(self):
        if len(self.heap_array) <= 1:
            return None
        
        returned_data = self.heap_array[1]
        self.heap_array[1] = self.heap_array[-1]
        del self.heap_array[-1]
        popped_idx = 1
        
        while self.move_down(popped_idx):
            left_child_popped_idx = popped_idx * 2
            right_child_popped_idx = popped_idx * 2 + 1

            # case2: ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ๋งŒ ์—†์„ ๋•Œ
            if right_child_popped_idx >= len(self.heap_array):
                if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                    self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]
                    popped_idx = left_child_popped_idx
            # case3: ์™ผ์ชฝ, ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ ๋ชจ๋‘ ์žˆ์„ ๋•Œ
            else:
                if self.heap_array[left_child_popped_idx] > self.heap_array[right_child_popped_idx]:
                    if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                        self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]
                        popped_idx = left_child_popped_idx
                else:
                    if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
                        self.heap_array[popped_idx], self.heap_array[right_child_popped_idx] = self.heap_array[right_child_popped_idx], self.heap_array[popped_idx]
                        popped_idx = right_child_popped_idx
        
        return returned_data
    
    def move_up(self, inserted_idx):
        if inserted_idx <= 1:
            return False
        parent_idx = inserted_idx // 2
        if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
            return True
        else:
            return False

    def insert(self, data):
        if len(self.heap_array) == 1:
            self.heap_array.append(data)
            return True
        
        self.heap_array.append(data)
        inserted_idx = len(self.heap_array) - 1
        
        while self.move_up(inserted_idx):
            parent_idx = inserted_idx // 2
            self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx]
            inserted_idx = parent_idx
        return True

 

๐Ÿฅฅ Heap ์‹œ๊ฐ„ ๋ณต์žก๋„

depth๋ฅผ h๋ผ๊ณ  ํ‘œํ˜„ํ•œ๋‹ค๋ฉด, n๊ฐœ์˜ ๋…ธ๋“œ๋ฅผ ๊ฐ€์ง€๋Š” heap์— ๋ฐ์ดํ„ฐ ์‚ฝ์ž… ๋˜๋Š” ์‚ญ์ œ ์‹œ,

์ตœ์•…์˜ ๊ฒฝ์šฐ root๋…ธ๋“œ์—์„œ leaf๋…ธ๋“œ๊นŒ์ง€ ๋น„๊ตํ•ด์•ผ ํ•˜๋ฏ€๋กœ h = log 2n์—

์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” ๐‘‚(๐‘™๐‘œ๐‘”๐‘›)์ด ๋ฉ๋‹ˆ๋‹ค.

ํ•œ๋ฒˆ ์‹คํ–‰์‹œ๋งˆ๋‹ค 50%์˜ ์‹คํ–‰ํ•  ์ˆ˜๋„ ์žˆ๋Š” ๋ช…๋ น์„ ์ œ๊ฑฐํ•œ๋‹ค๋Š” ์˜๋ฏธ์ž…๋‹ˆ๋‹ค.

์ฆ‰ 50%์˜ ์‹คํ–‰์‹œ๊ฐ„์„ ๋‹จ์ถ•์‹œํ‚ฌ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

Comments