블로그 이사 중입니다 >> gumgood.github.io

Priority Queue & Heap 본문

Problem Solving/분류없음

Priority Queue & Heap

gumgood 2017. 5. 27. 02:13

- prioiry queue : 우선순위가 가장 높은 순으로 pop하는 queue

- heap : maximum(or minimu) element를 차즌ㄴ데 최적화된 binary tree


1. priority queue 구현 종류

  ① linked list : push , pop 

  ② balanced BST : push , pop 

  ③ heap : push , pop 


  pq는 heap으로 쉽게 구현된다. 대부분 언어의 표준 라이브러리에 구현이 되어있다.


2. heap의 정의 (binary heap)

  heap은 '특정한 규칙'을 만족하도록 구성된 binary tree이다.

    ① 부모 node의 element는 자식 node의 element 크기 이상이다.

        (왼쪽, 오른쪽 관계는 상관없다. 오직 maximum element를 찾는데 집중한다)

    ② heap의 모양은 다음 두 조건을 따른다.

      - 마지막 level을 제외한 모든 level에 node가 꽉 차있어야 한다.

      - 마지막 level에 node가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 한다.

        (이 조건들은 tree가 가장 이상적인 형태를 띄도록 도와준다.)


  heap의 두번째 규칙은 대부분의 balanced BST보다 엄격한 조건이다. tree의 node 갯수만으로

  tree의 모양이 정해진다. 따라서 heap의 높이는 이다.

  tree 모양에 관한 조건이 엄격한 대신, '대소관계' 조건이 BST의 조건보다 느슨하다.


3. heap의 구현

  ① prioriy queue의 기능만 필요한 경우 STL을 쓰자

  ② heap의 추가적인 연산(ex, 원소 중 하나의 값을 바꾸기)이 필요한 경우 직접 구현한다.

      (크고 아름다운 배열을 쓰자)

'Problem Solving > 분류없음' 카테고리의 다른 글

Segment Tree (구간 트리)  (0) 2017.05.27
Disjoint-set  (0) 2017.05.27
Diameter of tree  (0) 2017.05.27
Tree Traversal  (0) 2017.05.27
Treap  (0) 2017.05.27
Priority Queue & Heap  (0) 2017.05.27
0 Comments
댓글쓰기 폼