자료구조 - Heap

chance·2020년 5월 22일
0

자료구조

목록 보기
2/6

학교에서 진행되는 자료구조 수업을 듣고 중요한 부분 위주로 정리하였습니다. 내용 상에 오류가 있다면 댓글로 피드백 부탁드립니다!

Priorty Queue

  • insertion sort와 selection sort로 데이터를 정렬할 수 있습니다.
  • list에 한번 insert하는데 O(n)의 시간이 걸리고 데이터의 개수가 n개이므로 O(n2)O(n^2)의 시간이 걸립니다.
  • heap을 사용한다면 O(nlogn)O(nlogn)의 시간만에 빠르게 정렬할 수 있어 list-based보다 heap-based priority queue가 효율적이라 배웁니다.

Heap이란?

두가지 조건을 만족시키는 자료구조

  1. heap-order property: 저장되는 key간의 관계가 일정하게 유지된다.
  2. complete binary tree: 마지막 level을 제외하고는 모두 채워져있으며 마지막 레벨의 노드는 왼쪽에서부터 채워진 트리
  • full binary tree: 노드의 자식이 오직 0개 또는 2개인 트리

특징

  • 마지막 level에서 가장 오른족에 있는 노드를 last node라 부른다.
  • min heap: parent node의 key는 child node보다 작거나 같다
  • max heap: parent node의 key는 child node보다 크거나 같다
  • 트리의 높이 h = [O(nlogn)][O(nlogn)]

Operations

Insertion

  • 새로운 last node를 추가
  • heap-order property를 복원하기 위해 up-heap bubbling을 해주어야 한다.
    up-heap bubbling: min heap일 경우, 추가된 last node의 entry의 key가 부모보다 작을 때까지 swap을 진행

Removal

  • removeMin: root node와 last node를 swap하고 last node를 제거
  • heap-order property를 복원하기 위해 down-heap bubbling을 해주어야 한다.
    down-heap bubbling: min heap일 경우, 변경된 root node의 entry의 key가 부모보다 클 때까지 swap을 진행

Updating the last node

  • tree-based heap을 만들었을 경우 필요하다. array-based heap의 경우에는 last node를 인덱싱을 통해 업데이트가 가능하여 필요하지 않다.

  • removal이 발생하였을 때 새로운 last node의 위치를 찾는 연산이다.

  • 로직

    1. 예전의 last 노드에서 시작한다.
    2. 예전의 last 노드를 포함하는 subtree가 right subtree가 될때까지 올라간다. 또는 루트 노드에 도달한다.
    3. 왼쪽 아래로 한번 이동하고 leaf node에 도달할 때까지 오른쪽 아래로 이동한다.
  • 시간복잡도: O(log(2n))=O(logn)O(log(2n)) = O(logn)

    Analysis of Heap-based PQ(Priority Queue)

  • insert: O(logn)O(logn): updating the last node + adding the last node + up-heap bubbling

  • remove: O(logn)O(logn): adding the last node + down-heap bubbling + updating the last node

    Heap Sort

    PQ를 Heap으로 구현할 경우

  • n번 데이터를 insert하고

  • n번 데이터를 remove합니다.
    다음과 같이 시간복잡도를 구할 수 있습니다.
    insert: $(n time insertion) O(logn) = O(nlogn)
    remove: $(n time removal)
    O(logn) = O(nlogn)
    따라서 총 시간 복잡도는 O(nlogn)입니다.

Array-based Heap

일반적인 binary tree를 array로 구현하였을 경우 skewed tree가 발생할 수 있어 O(2n)O(2^n)의 공간복잡도를 가질 수 있습니다. 따라서 자원을 굉장히 비효율적으로 사용하게게 될 수 있으나, complete binary tree의 경우에는 마지막 level을 제외하고는 모두 채워져서 공간을 효율적으로 사용할 수 있습니다. 또한 last node를 업데이트 할 필요없이 노드의 개수로 찾을 수 있어 O(1)의 시간이 걸린다는 것도 강점입니다. 추가적인 메모리 공간이 필요없는 in-place sort로 구현할 수 있습니다.

skewed tree: 한 쪽으로 노드가 치우쳐진 형태, leaf node를 제외한 모든 노드의 자식이 하나임, 선형적인 모양새

In-place heap sort

  1. 빈 heap에 element를 각각의 인덱스마다 채웁니다(한 element가 더해질 때마다 up-heap bubbling).
  2. root와 last node를 swap하고 down-heap bubbling을 합니다. 그 뒤에 last node로 사용되는 공간을 배제하고 그 전 인덱스의 노드가 새로운 last node가 되어 다시 swap을 하는 과정을 반복합니다.

Building a heap

  • 하나의 새로운 heap을 만드는 경우: 계속 insert와 up-heap bubbling을 하면 됩니다.
    successive insertions: O(nlogn)O(nlogn) time
  • 두개의 heap을 합치는 경우: 새로 만드는 것과 다른 방식으로 더 빠르게 heap을 만들 수 있습니다.
    bottom-up construction: O(n)O(n) time

Bottom-up construction

  • 힙 두개의 노드 개수만큼 채워지는 complete binary tree를 만든다.
  • 가장 낮은 0번째 height부터 element로 채운다.
  • 1번째 height부터는 element들은 down-heap bubbling이 이루어지도록 한다.
    Analysis
  • 한 노드는 최대 2번 방문되므로 노드의 총 방문 횟수 < 2n, 시간복잡도는 O(n)O(n)
profile
프론트엔드와 알고리즘을 주로 다룹니다.

0개의 댓글