자료구조 힙

자료구조 Heap

우선 순위 큐(데이터들은 우선순위를 가지고 있고, 높은 우선순위가 먼저 나간다.)를 위하여 만들어진 자료구조
배열, 연결리스트, 힙을 이용하여 힙을 구현할 수 있다.

  • 완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
  • 힙은 일종의 반 정렬 상태(느슨한 정렬 상태)를 유지한다.
  • 부모노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리

자료구조 Heap의 종류

  • 최대 힙(max heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
  • 최소 힙(min heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

Heap 구현 (배열)

  • 부모노드와 자식 노드의 관계
  • 0번째 배열 인덱스는 사용하지 않는다.
  • root 부모의 배열 인덱스는 1
  • 왼쪽 자식의 배열 인덱스 = 부모 배열 인덱스 * 2
  • 오른쪽 자식의 배열 인덱스 = 부모 배열 인덱스 * 2 + 1
  • 부모 배열 인덱스 = (자식의 배열 인덱스) / 2

Heap 삽입 (배열)

  1. 새로운 노드는 부모노드와 조건을 비교후 삽입한다.
  2. 마지막 노드까지 비교후 삽입이 완료된다.
  3. 마지막 노드에 도달하면, 부모 노드와 비교후 부모보다 클 경우 교환을 반복한다.

Heap 삭제 (배열)

  1. 최대 힙에서 최대값은 루트 노드이므로 루트 노드를 삭제한다.
  2. 루트노드에는 힙의 마지막 노드(배열의 마지막 위치 노드)로 교체한다.
  3. 루트노드를 자식노드와 비교하여 큰 값과 교체 하며 재구성한다.

사례

네트워크 트래필 제어
운영체제 작업 스캐줄링

자료구조 처리순서 비교

스택

  • 가장 최근에 들어온 데이터

  • 가장 먼저 들어온 데이터

    우선선위 큐(Priority Queue)

  • 우선순위가 높은 데이터