[패스트캠퍼스 수강 후기] {코딩테스트인강} 100% 환급 챌린지 50회차 미션

대표적인 데이터 구조8: 힙

1.     힙이란

-데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리

1.1  완전 이진 트리

-      노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

 

-      힙을 사용하는 이유

배열에 데이터를 넣고 최대값과 최소값을 찾으려면 O(n)이 걸림

이에 반해 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(logn)이 걸림

우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용

2.     힙 구조

-힙은 최대값을 구하기 위한 구조(=최대 힙) 와 최소값을 구하기 위한 구조(=최소힙)

-힙은 두가지 조건을 갖고 있는 자료구조

-      각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다(최대 힙 경우)

최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작다

-      완전 이진 트리 형태 갖습니다

-힙과 이진 탐색 트리의 공통점과 차이점

-      공통점: 힙과 이진 탐색 트리는 모두 이진 트리

-      차이점

힙은 각 노드의 값이 자식 노드보다 크거나 같다

이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 큽니다

힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없습니다

   힙의 왼쪽 및 오른쪽 자식 노드의 값은 오른쪽이 클 수 도 있고 왼쪽이 클 수도 있습니다

이진 탐샘 트리는 탐색을 위한 구조, 힙은 최대/최소값을 위한 구조 중 하나로 이해하면 됩니다

 

3.     힙 동작

- 데이터를 힙 구조에 삽입 ,삭제하는 과정을 그림을 통해 이해

-힙은 완전 이진 트리이므로 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입

 

힙에 데이터 삽입하기 – 기본동작

-      힙은 완전 이진 트리이므로 삽입할 노드는 기본적으로 최하단부 노드부터 채워진다

 

힙에 데이터 삽입하기 – 삽입할 데이터가 힙의 데이터보다 클 경우

-      먼저 삽입된 데이터는 완전 이진 트리 구조에 맞춰 최하단부 왼쪽 노드부터 채워진다

-      채워진 노드 위치에서 부모 노드보다 값이 클 경우 부모 노드와 위치를 바꾸는 작업 반복

 

힙의 데이터 삭제하기

-      보통 삭제는 최상단 노드를 삭제하는 것이 일반적

힙의 용도는 최대값 또는 최소값을 root노드에 놓아서 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것

상단의 데이터 삭제시, 가장 최하단부 왼쪽에 위치한 노드를 root 노드로 이동

root노드의 값이 child node보다 작을 경우 root 노드의 child node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업 반복

4. 힙 구현

힙과 배열

è 일반적으로 힙 구현 시 배열 자료구조를 활용

è 배열은 인덱스가 0번부터 시작하지만 힙 구현의 편의를 위해 root 노드 인덱스 번호를 1로 지정하면 구현이 좀 더 수월함

-      부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 //2

-      왼쪽 자식 노드 인덱스 번호  = 부모 노드 인덱스 번호 *2

-      오른쪽 자식 노드 인덱스 번호 = 부모 인덱스 번호 * 2 +1

-     

#예1 – 10 노드의 부모 노드 인덱스

   2//2

#예1 -15 노드의 왼쪽 자식 노드 인덱스 번호

1*2

          #예1 – 15 노드의 오른쪽 자식 노드 인덱스 번호

              2*2+1

힙에 데이터 삽입 구현 (Mas Heap 예)

      힙 클래스 구현1

    class Heap:

    def __init__(self, data):

        self.heap_array = list()

        self.heap_array.append(None)

        self.heap_array.append(data)

          

           heap = Heap(1)

heap.heap_array

           [None,1]

힙 클래스 구현2 – insert1

             인덱스 번호는 1번부터 시작하도록 변경

       

         class Heap:

    def __init__(self, data):

        self.heap_array = list()

        self.heap_array.append(None)

        self.heap_array.append(data)

    def insert(self, data):

        if len(self.heap_array) == 0:

            self.heap_array.append(None)

            self.heap_array.append(data)

            return True

        self.heap_array.append(data)

        return True

  힙 클래스 구현3 – insert2

-      삽입한 노드가 부모 노드의 값보다 클 경우 부모 노드와 삽입한 노드 위치를 바꿈

-      삽인 노드가 루트 노드가 되거나 부모 노드보다 값이 작거나 같을 경우까지 반복

-특정 노드 관련 노드 위치 알아내기

-      부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 //2

-      왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2

-      오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 +1

 

heap = Heap(15)

heap.insert(10)

heap.insert(8)

heap.insert(5)

heap.insert(4)

heap.insert(20)

heap.heap_array

-[ None, 20, 10, 15, 5, 4, 8]

class Heap:

    def __init__(self, data):

        self.heap_array = list()

        self.heap_array.append(None)

        self.heap_array.append(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) == 0:

            self.heap_array.append(None)

            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

힙에 데이터 삭제 구현 (Max Heap)

힙 클래스 구현4 -delete1

보통 삭제는 최상단 노드를 삭제하는 것이 일반적

-      힙의 용도는 최대값 또는 최소값을 root 노드에 놓아서 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것

class Heap:

    def __init__(self, data):

        self.heap_array = list()

        self.heap_array.append(None)

        self.heap_array.append(data)

   

    def pop(self):

        if len(self.heap_array) <= 1:

            return None

       

        returned_data = self.heap_array[1]

        return returned_data

 

 

 

   힙 클래스 구현4 – delete2

-      상단의 데이터 삭제시 가장 최하단부 왼쪽에 위치한 노드 ( 일반적으로 가장 마지막에 추가한 노드) 를 root노드로 이동

-      root 노드의 값이 child node 보다 작을 경우 root 노드의 child node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복 (swap)

특정 노드의 관련 노드 위치 알기

-      부모 노드의 인덱스 번호 = 자식 노드 인덱스 번호 //2

-      왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 *2

-      오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 *2 +1

 

heap = Heap(15)

heap.insert(10)

heap.insert(8)

heap.insert(5)

heap.insert(4)

heap.insert(20)

heap.heap_array

-출력: [None, 20, 10,15, 5, 4, 8]

강의에 대해 정확하게 알고 싶다면 

https://bit.ly/2FgOONG