[자료구조] Heap

우선순위 큐 (Priority Queue)

 

우선순위 큐란

• 자료구조 큐에 우선순위 개념을 도입
• 데이터가 들어온 순서에 따라 나가게 되는 큐, 스택과 달리 데이터들의 우선순위에 따라 나가는 순서가 달라진다
  ex: 물건 데이터를 자료구저에 넣었다가 꺼내는 경우, 가치가 높은 물건부터 꺼내서 확인

자료구조	삭제되는 요소
스택(Stack)	LIFO (Last in, first out)
큐(Queue)	FIFO(First in, first out)
우선순위큐(Priority Queue)	가장 우선순위가 높은 데이터

 

우선순위 큐의 구현

1. 단순히 리스트를 이용해 구현
2. 힙(heap)을 이용해 구현

배열, 연결 리스트, 힙으로 구현할 수 있지만 그 중 힙(heap)으로 구현하는 것이 가장 효율적

구현 방식	삽입시간	삭제시간
리스트	O(1)	O(N)
힙(heap)	O(logN)	O(logN)

---

자료구조 힙(Heap)

 

힙(Heap)의 특징

• 완전 이진 트리 자료구조의 일종 (루트 노드부터 시작해 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 삽입되는 트리)
• 힙에서는 항상 루트 노드(root node)를 제거
• 최소 힙(min heap)
  
  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같음
  • 루트 노드가 가장 작은 값을 가짐
  • 값이 작은 데이터가 우선적으로 제거됨
    

• 최대 힙(max heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같음
  • 루트 노드가 가장 큰 값을 가짐
  • 값이 큰 데이터가 우선적으로 제거됨

 

힙(Heap) 구현

• 표준적인 자료구조는 배열
• 쉬운 구현을 위해 0번 인덱스는 사용하지 않음
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않음
• 힙(heap)에서 부모 노드와 자식 노드의 관계
  • 왼쪽 자식의 인덱스 = 부모 인텍스 * 2
  • 오른쪽 자식의 인덱스 = (부모 인텍스*2) +1
  • 부모의 인덱스 = 자식 인덱스 %/% 2

 

 

 

 

 

1.  

 

 

 

 

 

힙(Heap)의 삽입

1. 힙(heap)에 새로운 요소가 들어오면 일단 마지막 노드에 이어 삽입
2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킴

O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있음

 

힙(Heap)의 삭제

1. 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제됨
2. 삭제된 루트 노드에 힙의 마지막 노드를 가져옴
3. 자식 노드와 비교하며 힙을 재구성

O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있음