[자료 구조] HEAP(힙)

HEAP(힙) 구조란? 힙 구조는 우선순위 큐를 구현하기 위해 주로 사용되는 자료구조로 다음의 정의를 따른다. Complete tree 마지막 level을 제외한 모든 level이 다 채워져 있고, 마지막 level은 왼쪽부터 삽입되는 트리 완전 이진 트리(Complete tree) max/min tree 자식 노드의 키 값이 루트 노드보다 크거나(max)/작거나(min) 하지 않은 트리 Max tree Min tree 표현 방식 힙 구조를 표현할때 주로 배열을 사용하도록 한다. 연결리스트를 사용해도 되겠지만 트리구조가 배열구조와 대응 되기 때문에 배열을 사용하며, 만약 배열로 표현 못하는 트리 구조(Complete하지 못한 트리)라면 연결리스트를 사용하여 표현해야 한다. 원소 삽입(Max heap 기준) 힙의 맨 끝에 원소를 추가한다 끝 원소를 그 부모 노드와 비교하여, 부모 노드가 값이 작으면 부모를 자식의 자리에 넣어준다. root에 도달하거나, 부모 노드의 값이 더 크면 br...

원문링크 : [자료 구조] HEAP(힙)