Heap, Priority Queue

https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

우선순위큐

  • 배열,연결리스트,힙 중 힙으로 구현 하는 것(lgN)이 가장 효율적

  • 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조
  • 여러 값들 중 최댓값이나 최솟값을 빠르게 찾아내도록 만들어짐
  • 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리
  • 힙 트리에서는 중복된 값을 허용 (이진 검색 트리에서는 비허용)
  • max heap – 부모노드 key >= 자식노드 key
  • min heap – 부모노드 key <= 자식노드 key

 

힙정렬

  • 자료구조인 힙을 이용
  • 힙 구성 후, 원소들을 다 삽입하고 하나씩 빼면서 배열의 앞에서부터 채워 넣으면 됨
  • min 힙의 경우 작은 수부터, max 힙의 경우 큰 수 부터 하나씩 나온다
  • 즉, 내림차순 정렬 – 최대힙, 오름차순 정렬 – 최소힙 사용
  • maxheap을 만들고, 오름차순이면 배열 뒤에서부터, 내림차순이면 앞에서부터 채우면 됨
  • 전체 자료를 정렬 하는 것이 아니라, 가장 큰 값 몇개만 필요할 때 매우 유용
  • 하나의 요소를 힙에 삽입/삭제 시 힙 재정비 시간이 log_{2}n 소요
  • 요소 개수가 n개 이므로 전체적으로 O(nlog_{2}n)

 

It's only fair to share...Share on Facebook
Facebook
Share on Tumblr
Tumblr
Share on Google+
Google+
Tweet about this on Twitter
Twitter
Email this to someone
email
Musicals, Travel, Photo, Coding, English, Cat