잡초의 일지

힙 (Heap) Heap은 완전 이진트리 (complete binary tree)를 기본으로 한다. 완전 이진트리란 이런 식으로 왼쪽정렬된 모습을 하는 트리이다. 자식이 추가되면, 오른쪽에 들어온다. 최대힙, 최소힙 ( Max_Heap , Min_Heap ) 힙에는 최대힙과 최소힙이 있다. 최대힙은 부모 노드의 값이 자식 노드의 값보다 크거나 같아야 한다. 최소힙은 그 반대이다. 이것이 최대힙의 예시이다. 이진 탐색 트리 (Binary Search Tree)와 헷갈릴 수 있으니, 조심해야 한다. 힙의 표현 힙은 배열이나 linked list로 만들 수 있다. 힙 노드 추가 (insert) 노드를 추가할 땐 오른쪽으로 추가한다. 이런 방식이다. 힙 노드 삭제 (delete) 힙 노드를 삭제할 때는 root..