자료구조 - 큐의동작 Chapter 6. Priority Queue(Heaps)

목차

1. Model, Simple Inplementations, Binary Heap
2. d-Heaps
3. Leftist Heaps
4. Skew Heap
5. Binomial Queue

본문내용

6.1 Model, 6.2 Simple Inplementations, 6.3 Binary Heap
 키값의 크기에 의해 정해지는 자료구조, 부모는 자식보다 크거나, 작다
 힙의 root는 가장 크거나 가장 작은 레코드가 된다.
 logN의 수행 시간을 보여준다. Heap Sort는 NlogN의 성능을 보인다
 h높이의 트리는 2h~2(h+1)-1의 노드를 갖는다

 트리구조를 배열로 구현
 번호 j를 갖는 노드의 부모 번호는 j/2
 번호 j를 갖는 왼쪽 자식의 번호는 j*2
 번호 j를 갖는 오른쪽 자식의 번호는 j*2+1
 힙 자료 개수 n의 절반(n/2)까지가 내부노드

 힙은 그 정의상 완전히 균형잡힌 나무구조를 나타낸다. 그러므로 연결리스트를 사용하면, 공간이 절약될 뿐만 아니라, 구현이 간단하고 속도도 향상될 수 있다.

 새로 삽입된 자료가 힙의 규칙에따라 지위가 상승하는 것을 UpHeap이라 부른다

참고 자료

없음