first-in, Smallest-First-Out(MinHeap)

first-in, Largest-First-Out(MaxHeap)

Priority Queue

출력시에 우선순위대로 나오는 것을 말함

종류

• heap

Heap

조건

degree 2인 2진 Tree

맨 위에는 최소나 최대값이 존재하는 degree=2인 2진tree

Parent & Child 조건

이때 parent >= child 의 조건만 만족하거나
parent <= child의 조건만 만족하면 된다.

Complete Binary Tree

모든 subtree가 꽉차있거나 오른쪽만 없는 상태인 Tree

Heap Sort

시험)
Heap Sort의 과정을 그리시오

1. 삽입할 때 Leaf부분에 Complete Binary Tree를 만족하도록 채워넣는다

2. 삽입한 후 Parent와 Child가 조건을 만족하도록 Parent와 Child의 값들을 바꾼다.

3. 같은 방법으로 모든 값들을 다 Heap에 삽입한다

4. 삽입한 후 맨위의 값을 빼낸다

5. Complete조건을 만족하기 위해 없어진 자리를 맨 오른쪽 Leaf로 대체한다.

6. 작은 값이 가장 위에 있어야 하므로 더 작은 값이랑 바꿔가면서 다시 자리를 찾아준다.

Hash

bucket을 활용해서 값들을 저장

예시) 1의자리수가 0~9까지의 bucket을 만든 후 값들을 저장

즉, 메모리가 커질수록(bucket이 커질수록) O(1)의 탐색속도를 가지게 됨 하지만, 메모리의 낭비가 심함

Hash Function

어떤 글자, 대상을 정수로 고치는 것

조건

1. 미리 조건을 정하고 bucket을 만들어 놓는다.

2. 어떤 대상을 Hash Function을 거쳐 정수로 만든다

3. 이 정수를 활용하여 bucket에 저장한다.
   이때 한 bucket에 많은 값들이 몰리는 것을 Collision이라고 함

(시험문제)

Collision 방지 대책

Double Hashing

1. hash Function을 2개 준비한다.

2. 1번 Hash Function을 사용하여 사용할 저장공간을 정한다.

3. 만약 해당 저장공간에 값이 있으면 2번 hashFunction을 사용하여 저장 공간을 얼만큼 이동해 줄 것인지 정한다.

4. 또 해당 공간에 값이 있으면 3번 반복

Radix Sort

1. 앞에서 부터 1의자리를 살펴보고 bucket에 넣는다.

2. 1의 결과를 가지고 다시 앞에서 부터 10의 자리를 살펴보고 bucket에 넣는다.

3. 2의 결과를 가지고 다시 앞에서 부터 100의 자리를 살펴보고 bucket에 넣는다

4. 반복

(단점)
자리수를 미리 알고있어야 함