힙이란? / What is the Heap Data Structure

- 완전 이진 트리의 일종

- 공간적인 구조를 단순히 배열의 인덱스를 적절히 부여함으로써 구현한다.

- 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

-  삽입, 삭제 속도 O(long n)

- 생산 속도 O(n)

- 힙은 일종의 반정렬 상태 (느슨한 정렬 상태) 를 유지한다.

- 힙 트리에서는 중복된 값을 허용한다.

 

힙(heap)의 종류

1. 최대 힙 (max heap)

루트 노드는 가장 큰 노드이다. 

부모 노드 >= 자식 노드

 

2. 최소 힙(min heap)

루트노드는 가장 작은 노드이다.

부모노드 <= 자식 노드

 

---

- A Heap is a special Tree-based data structure in which the tree is a complete binary tree.

- The heap structure uses an array to represent a tree.

- The heap can search maximmum or minnimum value quickly.

- The insert, and remove functions run in O(log n) time.

- The building of a heap has a run time of O(n)

- A Heap is not a sorted structure; it can be regarded as being partially ordered.

- A Heap can duplicate value

 

1. Max-Heap

The root node must be greatest among the keys present all of it's children.

parent node >= child node

 

2. Min-Heap

The root node must be minimum among the keys present at all of it's children.

parent node <= child node

 

참고사이트(Reference site)

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

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

 

www.guru99.com/stack-vs-heap.html

Stack vs Heap: Know the Difference

en.wikipedia.org/wiki/Heap_(data_structure)

Heap (data structure) - Wikipedia