[Data Structure] 비선형 - 힙(Heap)

#요약

• 우선순위 큐(Priority Queue)를 위해 만들어진 자료구조

※ 우선순위 큐 (Priority Queue) : 우선순위의 개념을 큐에 도입한 자료구조 데이터들이 우선순위를 갖고 있으며 우선순위가 높은 순서대로 높은 데이터가 pop 되는 구조 이용사례 1. 시뮬레이션 시스템 2. 네트워크 트래픽 제어 3. 운영 체제 스케듈링

#구체적 설명

• 완전 이진 트리로 우선순위 큐를 위해 만들어진 구조
• 여러개의 데이터 중 Minum 과 Maximum을 빠르게 찾을 수 있다.
• 느슨한 정렬(반정렬) 상태를 유지
• 중복된 값을 허용한다
• 힙의 종류
  • 최대 힙(Max Heap)
    • 부모 노드의 키 값이 자식 노드의 키값보다 크거나 같은 완전 이진 트리
    • key(부모 노드) >= key(자식 노드)
  • 최소 힙 (Min Heap)
    • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
    • key(부모 노드) <= key(자식 노드)
• 표준적인 자료구조인 배열을 통해 구현 ➡️0번째 인덱스 활용X
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변함X
• 연산 처리
  • 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
  • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
  • 부모의 인덱스 = (자식의 인덱스) / 2