728x90 최소힙2 힙[Heap], 삽입 및 삭제 힙 (Heap), 삽입 및 삭제 정의 최대힙/최소힙 ( Link : 2021.07.21 - [C++ Algorithm/ETC] - 힙 [Heap], 최대힙/최소힙 ) 에서 임의의 값을 삽입, 삭제할 때 O(logN) 의 시간복잡도로 해결을 할 수 있다. 이러한 1차원 array 에서는 임의의 값을 삽입하거나 삭제를 할 때 마다 O(N)의 시간이 소요가 되어 굉장히 비효율적이다. 최대힙/최소힙을 사용한다면 이는 이진트리로 이루어졌기 때문에 이 작업들이 O(logN)의 소요시간을 가진다. 삽입 최대힙/최소힙 에서 Data 의 삽입은 현재 Node중 가장 마지막 Node에 우선 연결이 된다. 힙(Heap)은 완전이진트리를 활용한 자료구조 이기에 삽입을 할 때 기존 Node 와 Swap을 하여 두지 않는 이상 .. 2021. 7. 22. 힙 [Heap], 최대힙/최소힙 힙 (Heap), 최대힙/최소힙 정의 힙(Heap) 이란 완전이진트리(Perfect Binary Tree) 를 응용한 자료구조이다. 완전이진트리는 아래와 같은 Binary Tree를 의미한다. 완전이진트리는, 위처럼 마지막 레벨을 제외하면 모두 포화상태이며 마지막 레벨에 해당되는 노드들은 모두 좌측으로 쏠려있는 Binary Tree 이다. 이를 이용해서 힙(Heap)이라는 자료구조에 접근을 할 수 있다. 예를 들어 만약 최소힙을 생성하게 되면, Parent node 는 항상 Child node 보다 작거나 같은 값을 가지게 된다. 설명 힙(Heap)은 일반적으로 어떠한 수의 배열에 있어서 최소값과 최대값을 구할 때 쓰인다. 최소값을 구할 때 쓰이는 힙(Heap)은 최소힙(Min Heap) 이라고 불리고 .. 2021. 7. 21. 이전 1 다음 728x90
