힙[Heap], 삽입 및 삭제

힙 (Heap), 삽입 및 삭제

---

 정의 

  최대힙/최소힙 ( Link : 2021.07.21 - [C++ Algorithm/ETC] - 힙 [Heap], 최대힙/최소힙 ) 에서 임의의 값을 삽입, 삭제할 때 O(logN) 의 시간복잡도로 해결을 할 수 있다.

 

 

  이러한 1차원 array 에서는 임의의 값을 삽입하거나 삭제를 할 때 마다 O(N)의 시간이 소요가 되어 굉장히 비효율적이다. 최대힙/최소힙을 사용한다면 이는 이진트리로 이루어졌기 때문에 이 작업들이 O(logN)의 소요시간을 가진다.

---

 삽입 

  최대힙/최소힙 에서 Data 의 삽입은 현재 Node중 가장 마지막 Node에 우선 연결이 된다. 힙(Heap)은 완전이진트리를 활용한 자료구조 이기에 삽입을 할 때 기존 Node 와 Swap을 하여 두지 않는 이상 그 곳 밖에 우선 둘 곳이 없을 것 이다.

 

  아래 최대힙을 예시로 Data의 삽입을 설명 해 보았다.

 

새로운 Data인 8을 Node 10 에 삽입을 하였다.

  새 data를 마지막 Node에 삽입을 하였다. 우선 삽입의 가장 첫 작업을 한 것이고 이제 삽입된 노드로부터 계속해서 부모노드와 비교를 해 갈 것이다. 최대힙이므로, 부모노드가 현재노드보다 작으면 Swap이 이루어지고 부모노드가 현재노드보다 크거나 같으면 더이상 Swap이 이루어지지 않을 것 이다.

 

5번째 Node 와 10번째 Node 의 Swap

  10 번째 Node 에 삽입이 된 data 8 은 부모노드의 값보다 크다. 따라서 이와 같이 두 Node 의 Swap이 이루어졌다. 그 결과 삽입된 Node는 현재 5번째 Node 에 있다.

 

  5번째 Node 에 있던 data 8은 그 Node 의 부모노드인 2번째 Node 의 data인 7보다 크므로 위와 같이 또 두 Node가 Swap이 되었다. 그리고 2번째 Node 로 옮겨진 삽입되었던 Node 는 이제 본인보다 큰 data를 가진 부모노드를 만났으므로 이제 Node의 Swap을 멈춘다. 위 그래프가 삽입을 한 그래프의 최종 결과인 것이다.

---

 삭제 

  새 Data 를 삽입을 할 땐 항상 마지막 Node 에 임의의 Data를 삽입을 하였다. 힙에서 Data 의 삭제는 항상 루트 노드를 삭제를 한다. 최대힙의 경우엔 최대값이 삭제가 되는 것 이고 최소힙의 경우엔 최소값이 삭제가 되는 것 이다. 

 

  최대힙/최소힙을 활용한 STL인 우선순위큐(Priority queue)의 성질이 이러한 최대힙/최소힙의 삽입 및 삭제 성질을 가진 것을 생각해 볼 수 있다. 우선순위큐 또한 임의의 data 삽입이 가능하며, data의 삭제는 항상 우선순위큐 정렬기준에 따라 최소값 혹은 최대값만 삭제가 가능하기 때문이다.

 

  아래 예시로 최대힙의 data 삭제를 설명 해 보았다.

 

루트 노드를 제거 할 것이다.

  위 루트 노드를 제거 할 것 이다. 

 

  제거가 된 후에 가장 마지막 Node가 루트노드로 이동을 한다.

 

  가장 마지막에 있던 Node가 루트노드로 이동을 하였다. 루트노드로 이동을 한 후 최대힙 조건을 갖춰야 하므로 계속해서 자식 Node 와 비교를 해가면서 필요시 Swap을 한다.  현재 루트노드의 값은 아래 두 자식노드보다 작다. 이 경우 두 자식노드 모두 루트노드와 Swap이 가능하다. 이러한 경우엔 최대힙인 경우는 두 자식노드중 더 큰 값을 가지는 노드가, 최소힙인 경우는 두 자식노드중 더 작은 값을 가지는 노드가 부모노드와 Swap이 이루어진다.

 

  위와 같이 두 Node의 Swap이 이루어졌다. 그리고 2번째 Node로 이동이 된 Node는 또 다시 자식 Node들과 값을 비교한다. 2번째 Node는 아래 두 자식노드들보다 작은 값을 가지고 있다. 따라서 아까와 마찬가지로 두 자식노드들 중 더 큰 값을 가지는 자식 Node와 Swap을 한다.

 

  우측 자식노드와 Swap이 이루어졌다. 그리고 마침내 아래와 같이 삭제 후 최대힙 그래프가 구현이 완료가 되었다.

 

 

---

 Code 

// 삽입
void insert(vector<int>& maxHeap, int curNode) { // data가 삽입 된 Node로 curNode 입력
	if (curNode == 1) {
		return;
	}
	else { // if this is not root node ( compare with parent node )
		while (curNode / 2) {
			int parentNode = curNode / 2;

			if (maxHeap[parentNode] < maxHeap[curNode]) {
				int temp = maxHeap[parentNode];
				maxHeap[parentNode] = maxHeap[curNode];
				maxHeap[curNode] = temp;
			}

			curNode /= 2;
		}
	}
}

// 삭제
void remove(vector<int>& maxHeap, int heapSize) {
	maxHeap[1] = maxHeap[heapSize]; // 마지막 Node 를 Root Node 로
	maxHeap[heapSize] = 0; // 위에서 마지막 Node 를 옮겼으므로 이를 0으로 초기화
	heapSize--; // 마지막 노드를 삭제 하였으므로 Size--

	int curNode = 1; // 삭제 후 Node 재정비를 시작하는 Node 번호
	int changeNode = 0; // 
	int leftChild, rightChild;

	while (2 * curNode <= heapSize) {
		leftChild = maxHeap[2 * curNode];
		rightChild = 2 * curNode + 1 <= heapSize ? maxHeap[2 * curNode + 1] : 0;

		if (rightChild) {
			if (leftChild > maxHeap[curNode] && rightChild > maxHeap[curNode])
				changeNode = leftChild > rightChild ? 2 * curNode : 2 * curNode + 1;
			else if (leftChild > maxHeap[curNode])
				changeNode = 2 * curNode;
			else if (rightChild > maxHeap[curNode])
				changeNode = 2 * curNode + 1;
		}
		else // leftChild
			if (leftChild > maxHeap[curNode])
				changeNode = 2 * curNode;

		if (changeNode) {
			int temp = maxHeap[curNode];
			maxHeap[curNode] = maxHeap[changeNode];
			maxHeap[changeNode] = temp;

			curNode = changeNode;
			changeNode = 0;
		}
		else break;
	}
}