우선순위 큐와 힙의 차이

쉬운코드님 강의들 듣고 정리했습니다! 문제 시 삭제할게요

1. Priority queue(우선순위 큐)

🍇 개념

• 큐와 유사하지만 우선순위가 높은 아이템이 먼저 처리됨

🍇 우선순위 큐 주요 동작

1. insert : 아이템 우선 순위 순으로 넣어줌

2. delete : 가장 우선 순위가 높은 것을 빼냄

3. peek : delete와 같지만 우선순위 큐에서 제거는 안함

🍇 우선순위 큐 동작 방식 설명

1. delete를 호출하면 우선순위가 가장 높은 20이 사라지게 됨

2. 두 번째로 delete를 호출하면 우선순위가 높은 10이 사라지게 됨

3. 또 delete를 호출하면 5기 사라지게 된다.

2. Heap

🍇 힙의 개념

• 주로 이진 트리 기반으로 구현이 됨

• 트리(tree) : 부모 - 자녀처럼 계층적인 형태를 가지는 구조

• 이진 트리 : 자녀가 최대 두 개인 트리

max heap

• 부모 노드의 키가 자식 노드의 키보다 크거나 같은 트리

• 서브트리도 마찬가지로 적용되어야 함

min heap

• max heap의 반대

🍇 힙 주요 동작

1. insert : 힙의 아이템을 집어넣을 때 키값도 같이 넣어줘야 함

2. delete : 키 값이 가장 큰 값을 빼냄

3. peek : delete와 같지만 꺼내지는 않는다.

🍇 max heap의 insert 동작 원리 설명

1. max heap에서 inert(17)하면 11번째 공간에 일단 17이라는 값을 넣음

2. 부모보다 더 크기 때문에 3이랑 스위칭

3. 15와 또 비교해줌

4. 20이랑 비교 후 자리 안 바꿔도 돼서 끝이 남

🍇 max heap의 delete 동작 원리 설명

1. 루트 노드의 키 값이 트리 중에 가장 큼 ⇒ 삭제를 할 때 루트 노드가 사라짐

2. 그럼 뭐를 루트노드로 올릴까?

3. 그리고 max heap을 유지시켜주기 위해 자녀와 비교해서 체인지 해줘야 함

• 15, 11모두 2보다 크기에 그 중 더 큰 15를 루트 노드로 올림

4. 또 자녀와 비교

• 12, 3 모두 2보다 큰데 12가 더 크기 때문에 12와 체인지

5. 마찬가지 자녀와 비교

• 7과 5모두 2보다 큰데 그 중 더 큰 7을 위로 올린다.

3. priority queue와 Heap의 관계

🍇 관계

1. 힙(Heap)의 키(key)를 우선순위(priority)로 사용한다면, 힙은 우선순위 큐(priority queue)의 구현체가 된다.

2. Priority queue = ADT(구현을 설정하지 않고 개념적인 것만 설명)

   1. 추상 자료형(abstract data type)

   2. 추상 자료형은 구현 방법을 명시하고 있지 않다는 점에서 자료 구조와 다르다. 비슷한 개념의 추상적 자료 구조는 각 연산의 시간 복잡도를 명기하고 있지만 추상적 자료형에서는 이것조차 명기하지 않는다.

   3. 추상 자료형은 인터페이스와 구현을 분리하여 추상화 계층을 둔 것이다. 예를 들어 전기 밥솥을 추상 자료형에 비유한다면 그 속에 들어가는 밥은 자료가 되고, 밥솥에 있는 취사, 예약취사 버튼들과 남은 시간을 표시하는 디스플레이에 어떤 내용들이 표시되어야 하는지를 명기한 것이다.

3. Heap = data structure(구현까지 있음)

4. 우선순위 큐를 구현하기 위해 다양한 것들이 있겠지만, 힙을 대체로 많이 사용해서 동일시 하는 사람들이 있다.

4. 우선순위 큐와 힙의 사용 사례

🍇 프로세스 스케줄링(process scheduling)

1. cpu에서 현재 동작하고 있는 프로세스가 p1이라면 p2, p3, p4는 대기해야 하는데 대기할 때, ready queue에 대기한다.

2. 근데 ready queue가 FIFO이 아니라 우선순위 큐라면 P1이 cpu 작업을 다 끝냈을 때, 들어온 순이 아니라 우선순위가 높은 애가 먼저 작업을 하게 됨

🍇 heap sort(힙 정렬)

1. 정렬 n개의 아이템 ⇒ 힙에 다 넣어서 차례차례 delete() 시 정렬되어서 나오게 됨

🍇 Heap 메모리도? 힙과 같나..?

• No, 힙 메모리의 힙은 오늘 배운 힙과는 관련이 없다

• 힙 메모리의 힙은 메모리에 있는 더미 느낌

힙 메모리

1. 스택 메모리의 단점 보완

   1. 수명 : 스택 메모리의 경우 함수가 반환되는 순간 그 안에 있던 데이터가 다 날라가며, 전역 변수는 언제나 살아있고, 지역 변수는 함수 안에서만 유효

   2. 크기 : 스택메모리는 특정 용도로 떼어놓은 것이라 크기가 작다. 용량의 제한적

2. 힙 메모리의 장점[unmanaged]

   1. 크기 : 컴파일러 및 CPU가 자동적으로 메모리 관리를 안 해주기 때문에 프로그래머가 원하는 때, 원하는 만큼 메모리 할당받아와 사용하고 원할 때 반납(해제) 할 수 있다.

   2. 용량 제한 없음 : 프로그래머가 데이터의 수명을 직접 제어할 수 있어, 컴퓨터에 남아있는 메모리만큼 사용 가능 ⇒ 호출이 끝난다고 사라지지 않는다.

3. 힙 메모리의 단점

   1. 메모리 누수 위험성 있음 : 매니지드 언어인 JAVA는 메모리 할당받을 때 new 키워드 사용하며, 사용 후에는 해제 신경을 안쓴다. 메모리 해제를 알아서 해주기 때문이다. 하지만 c는 언매니지드라 프로그래머가 직접 해줘야 한다.

   2. 스택에 비해 할당/해제 속도가 느림 : 함수가 요청한 만큼의 크기 빈 공간을 찾으려고 이리저리 찾아야 한다.

스택 메모리 vs 힙 메모리

스택 메모리	힙 메모리
정적 메모리	동적 메모리
오픈셋 개념으로 정확히 몇 바이트씩 사용해야 하는지 컴파일 시 결정	실행 중에 크기와 할당/해제 시기가 결정됨