Heap

본 문서는 2021년 12월 28일 에 작성되었습니다.
또한 매우 간단한 설명과 Ref 만을 걸어 놓고 있습니다.

Heap 이라는 자료 구조는 매우 특수한 자료 구조입니다.
완전 이진 트리 의 일종이며 최댓값 및 최솟값 계산에 특화 되어 있습니다.

이를 통해서 일반적으로 Prioiry Queue 라는 자료 구조를 만들 수 있으며,
시뮬레이션, 네트워크 트레픽 제어, 수치 해석적 계산 등에 쓰이고 있습니다.

이에 따라서, 이 자료구조의 학습 목적은 매우 특별합니다.
작성일 기준으로 Heap Sort 을 공부하기 위해서 정리한 내용입니다.

Heap 을 알기 전에...

ArrayList의 장점 및 단점 와 Java : Collection Framework 중 ArrayList 에서 알아봤듯이,
(ArrayList) Java 에서 배열은 데이터의 삽입 및 삭제에서 취약했기에 Node 라는 개념이 추가되어서 여러 가지 자료구조 등이 생겨났습니다.

이를 통해서 LinkedList 라는 것이 만들어 졌는데,
LinkedList의 장점 및 단점 과 Java : Collection Framework 중 LinkedList 에서 알아봤듯이, 이 또한 읽기 면에서 안좋은 단점을 가지고 있었습니다.

하지만 Collection Framework 를 사용한다면 이 두 타입을 변환 할 수 있기 때문에,
읽기 작업에서는 ArrayList 를 삽입 및 삭제 작업에서는 Linked List 를 권고했습니다.

그래서 만들어진 것이 바로 Tree 구조 입니다. 사진 출처 : 위키백과

위와 같이 Tree 구조 는 OOP 상속도와 같이 부모와 자식이 구분됩니다.
둘 을 연결하는 것을 역시 Node 라고 부르며 일반적으로 일방향 방향성을 가집니다.
이 때, 하나의 대상이 최대 2개의 Node 를 가지는 것을 이진 Tree 구조 라고 합니다.

그리고 Heap 은 이진 Tree 구조 의 일종입니다.

Heap 이란?

Heap 은 앞서 말했듯, 완전 이진 트리의 일종입니다.
이러한 Heap 의 특징은 다음과 같습니다.

1. n 개의 값 중 최댓값 및 최솟값 검색에 탁월합니다.
2. n 개의 값에 대한 느슨한 정렬 상태를 유지합니다.
3. n 개의 값 중 중복값 존재를 허용합니다.
   3.1. Binary Tree Strcuture 에서는 불허한다는 것이 특징입니다.

Heap 의 종류?

Heap 은 두 가지 종류가 존재합니다.

1. Max Heap
2. Min Heap

Heap 의 구현? 삽입? 삭제?

Heap 도 표준 자료구조인 배열을 사용하며, 구현 난이도 탓에 index 0 은 사용되지 않는다.

자세한 내용은 [자료구조] Heap 이란? 중 Heap 의 구현 을 참고하자.

Ref

[자료구조] Heap 이란?