자바의 자료구조 - Heep

역시나 순서는 이상한 기분이지만 크게 지장은 없을 듯 하다.

곱셈을 배우고 덧셈을 배우면 아 이렇게 곱셈에 쓰였구나 할 수도 있으니 앞으로도 나오는

자료구조 포스팅을 참고하면 좋을 듯 하다. 

 

 : Heep은 우선순위 개념을 Queue에 이용하여 만들어진 자료구조이다. 

     데이터들이 우선순위를 가지고 있고, 우선순위가 높은 데이터를 먼저 배출한다. 

     우선순위 큐는 배열, 연결리스트, 힙 으로 구현이 가능하다. 

     이 중에서 힙(heap)으로 구현하는 것이 가장 효율적이다.

     완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조다.
     여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내기 위한 자료구조이며,
     힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다.
     큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
     간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
     힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)

 

 : 최대 힙(max heap)
부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
key(부모 노드) >= key(자식 노드)

 : 최소 힙(min heap)
부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
key(부모 노드) <= key(자식 노드)

 : 힙을 저장하는 표준적인 자료구조는 배열 이다.
     구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
     특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
     예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
       힙에서의 부모 노드와 자식 노드의 관계
     왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
     오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
     부모의 인덱스 = (자식의 인덱스) / 2

 

 

 : 이러한 Heap을 어떻게 만드는지 보자.

     어떤 리스트에 값을 넣었다가 빼낼려고 할 때,

     우선순위가 높은 것 부터 빼내려고 한다면 대개 정렬을 떠올리게 된다.

     쉽게 생각해서 숫자가 낮을 수록 우선순위가 높다고 가정할 때

     매 번 새 원소가 들어올 때 마다 이미 리스트에 있던 원소들과 비교를 하고 정렬을 해야한다.

     문제는 이렇게 하면 비효율적이기 때문에 좀 더 효율이 좋게 만들기 위하여 다음과 같은 조건을 붙였다.

     '부모 노드는 항상 자식 노드보다 우선순위가 높다.'

 

 : 힙의 삭제와 추가에 대해서는 그림까지 잘 나와있는 다음의 블로그를 참고하자.

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

[자료구조] 힙(heap)이란 - Heee's Development Blog

 

 : 우선순위 큐의 이용 사례
     시뮬레이션 시스템
     네트워크 트래픽 제어
     운영 체제에서의 작업 스케쥴링
     수치 해석적인 계산