Heap

Heap은 Binary Tree를 활용한 응용된 Tree계열의 자료구조 입니다. 

 

Left부터 채워넣은 완전 이진Tree이며, 상위 Node로 갈 수록 Max Or Min 값을 보여주는 Tree입니다.

 

이때 Max_heap과 Min_heap이 있으며, 아래 예시를 보면 이해하기 쉽습니다.

 

Random한 Array를 Max Heap 또는 Min Heap을 만들었을 경우의 모습입니다. 따로 설명이 필요없어보이네요

 

이때 Tree구조를 언어에서 표현하는 방법으로 Pointer 방식과 List 방식이 있는데, List 방식으로 구현하도록 하겠습니다.

 

List로 구현된 Tree구조

List로 구현할 경우, i번째의 Node는 2i+1, 2i+2번째 노드의 부모Node가 됩니다.

(Ex, 위의 1번째 Node는 3, 4번째 Node의 부모Node임)

 

따라서 Random한 Array를 가지고,  마지막 원소부터 (N-1)/2의 정부부분(3.5면 3) Node와 비교를하면 Heap의 구조와 가까워 지게 됩니다. 

 

이때 중요한점이 한차례의 비교 결과 0번 Node에는 항상 Max값을 갖게 됩니다.

 

하지만, 한번의 비교로는 완벽한 Heap이 구축되지 않기 때문에, Max Heap형태의 자료구조가 필요할 경우

 

Max Heap이 완성될때까지 비교를 반복합니다.(Max Depth 만큼 반복된다고 보시면 됩니다)

 

Max Heap에서 Element를 추가 or 삭제할때는 어떻게 할까요?

Heap에 새로운 Element추가

element의 추가의 경우, 마지막 Node에 새로운 Element를 추가하고, 해당 Node의 부모노드와 Depth만큼 비교를 하면 됩니다.

 

삭제의 경우 이야기가 다릅니다.

 

Element를 삭제할 경우, 마지막 Node와 위치 변경 후 해당 해당 Element는 삭제하고,

 

Swap한 Node부터 값이 큰 Node를 따라 Leaf Node를 찾고, 해당 Node로 부터 부모Node와 비교를 진행합니다.

 

Heap의 Element 삭제 Sequence

Python으로 구현한 Max_Heap 소스코드입니다 :)

import random
import math
import copy


class max_heap:
    def __init__(self, DT_list):
        self.ori_data = DT_list
        self.max_depth = 0
    
    def make_Max_heap(self):
        Max = len(self.ori_data)    
        while True:
            test_list = copy.deepcopy(self.ori_data)
            #Leap Node층부터 부모Node와 비교            
            for i in range(Max):                                        
                if Max-1-i != 0:                    
                    if self.ori_data[Max-1-i] > self.ori_data[math.floor(1/2*(Max-2-i))]:
                        temp = self.ori_data[Max-1-i] 
                        self.ori_data[Max-1-i] = self.ori_data[math.floor(1/2*(Max-2-i))]
                        self.ori_data[math.floor(1/2*(Max-2-i))] = temp        
            #Heap 생성 진행 후 변화가 없으면 Heap이 완성되었으므로 알고리즘 종료            
            if test_list == self.ori_data:
                return self.ori_data

    
    def add(self, element):
        self.ori_data = self.ori_data + [element]
        depth = self.refresh_depth()        
        while True:            
            start_index = len(self.ori_data)-1            
            test_list = copy.deepcopy(self.ori_data)
            #추가된 Node의 Line만 비교
            for i in range(depth):                
                if self.ori_data[start_index] > self.ori_data[math.floor(1/2*(start_index-1))]:
                    temp = self.ori_data[start_index]
                    self.ori_data[start_index] = self.ori_data[math.floor(1/2*(start_index-1))]
                    self.ori_data[math.floor(1/2*(start_index-1))] = temp
                start_index = math.floor(1/2*(start_index-1))
            if test_list == self.ori_data:
                return self.ori_data
            
    def delete(self, element):        
        validation = False
        for j in range(len(self.ori_data)):
            if self.ori_data[j] == element:
                validation = True
                temp = self.ori_data[-1]
                self.ori_data[-1] = self.ori_data[j]
                self.ori_data[j] = temp
                del(self.ori_data[-1])
                break
        if validation == False:
            return "there are no element matched"
                
        depth = self.refresh_depth()            
        start_index = j
        while True:                
            if start_index*2+1 <=len(self.ori_data)-1:
                if self.ori_data[start_index*2+1] > self.ori_data[start_index*2+2]:
                    start_index = start_index*2+1             
                else:
                    start_index = start_index*2+2             
            else:
                break                    
        while True:                
            start_inital_index = copy.deepcopy(start_index)
            test_list = copy.deepcopy(self.ori_data)
            for i in range(depth):                                
                if self.ori_data[start_inital_index] > self.ori_data[math.floor(1/2*(start_inital_index-1))]:
                    temp = self.ori_data[start_inital_index]
                    self.ori_data[start_inital_index] = self.ori_data[math.floor(1/2*(start_inital_index-1))]
                    self.ori_data[math.floor(1/2*(start_inital_index-1))] = temp
                start_inital_index = math.floor(1/2*(start_inital_index-1))
            if test_list == self.ori_data:
                return self.ori_data
        
        
    def refresh_depth(self):
        self.max_depth = 0        
        Max = len(self.ori_data)
        while True:
            Max = Max-pow(2,self.max_depth)            
            if Max<=0:
                break
            self.max_depth = self.max_depth+1            
        return self.max_depth
        
    
Data = [5,12,9,3,2,1,8,0,7,4,13,10,6,14,11] 

test = max_heap(Data)

test.make_Max_heap()
==> [14, 13, 11, 7, 12, 10, 9, 0, 3, 4, 2, 6, 1, 8, 5]

test.add(50)
==> [50, 14, 11, 13, 12, 10, 9, 7, 3, 4, 2, 6, 1, 8, 5, 0]

test.delete(14)
==> [50, 13, 11, 7, 12, 10, 9, 0, 3, 4, 2, 6, 1, 8, 5]

test.delete(100)
==> 'there are no element matched'

 

이때 이 Heap 자료구조를 이용한 정렬 알고리즘이 Heap Sort입니다

teus-kiwiee.tistory.com/18

Heap Sort