[자료구조] 힙(Hip)한 힙(Heap)

정의

힙은 우선순위 큐를 구현하기 위하여 만들어진 자료구조이다. (우선순위 큐는 자료구조가 아닌 개념이다.)

우선순위 큐를 구현하는 방법에는 배열, 연결리스트, 힙 이렇게 3가지 방법이 있는데 이 중에서 힙이 가장 효율적이다.

우선순위 큐 구현 방법	삽입	삭제
순서 없는 배열	O(1)	O(n)
순서 없는 연결 리스트	O(1)	O(n)
정렬된 배열	O(n)	O(1)
정렬된 연결리스트	O(n)	O(1)
힙	O(log n)	O(log n)

 

 

힙은 최대값과 최소값을 빠르게 찾아내도록 만들어졌고, 반정렬 상태이다.

(큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다 정도)

 

A가 B의 부모 노드면, A와 B의 키 값 사이에는 대소 관계가 성립한다.

자료의 삽입, 삭제 후엔 항상 힙이 유지할 수 있도록 재구조화(heapify)하는 과정이 필요하다.

 

 

 

종류

루트가 가장 큰 값인 최대 힙(Max Heap)과 루트가 가장 작은 값인 최소 힙(Min Heap)이 있다.

이미지 출처 https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

최대 힙(Max Heap)

key(부모 노드) >= key(자식 노드)

 

최소 힙(Min Heap)

key(부모 노드) <= key(자식노드)

 

 

구현

힙으로 우선순위 큐를 구현하기 전에 배열로 우선순위 큐를 먼저 구현해보자.

정렬된 배열에서 삽입을 할 땐 O(n), 삭제를 할 땐 (O(1)의 시간복잡도를 갖는다.

 

class PriorityQueue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    let contain = false;

    for (let i = 0; i < this.items.length; i++) {
      if (this.items[i] > element) {
        this.items.splice(i, 0, element); // i번째 값을 element로 변경
        contain = true;
        break;
      }
    }
    if (!contain) {
      this.items.push(element);
    }
  }

  dequeue() {
    if (this.isEmpty()) return "큐가 비었습니다..";
    return this.items.shift();
  }

  front() {
    if (this.isEmpty()) return "큐가 비었습니다..";
    return this.items[0];
  }

  rear() {
    if (this.isEmpty()) return "큐가 비었습니다..";
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  printPQueue() {
    for (let i = 0; i < this.items.length; i++) {
      this.items[i].element;
    }
    return this.items;
  }
}

const priorityQueue = new PriorityQueue();

console.log(priorityQueue.isEmpty()); // true
console.log(priorityQueue.front()); // 큐가 비었습니다..

// 요소 추가
priorityQueue.enqueue(2);
priorityQueue.enqueue(1);
priorityQueue.enqueue(1);
priorityQueue.enqueue(2);
priorityQueue.enqueue(3);

console.log(priorityQueue.printPQueue()); // [1,1,2,2,3]

// 가장 높은 우선순위 반환
console.log(priorityQueue.front());

// 가장 낮은 우선순위 반환
console.log(priorityQueue.rear());

// 가장 높은 우선순위 삭제
console.log(priorityQueue.dequeue());

// 요소 2 추가
priorityQueue.enqueue(2);

console.log(priorityQueue.printPQueue()); // [1,2,2,2,3]

삽입하는 과정에서 먼저들어간 요소들과 비교를하여 정렬을 해야한다. 배열요소 하나하나를 검사해야하기 때문에 시간복잡도는 배열의 길이만큼인 O(n)이 된다.

 

다음은 연결리스트로 구현한 우선순위 큐다. 이 예시에선 삽입하면서 정렬을 하기 때문에 위의 배열과 마찬가지로 삽입을 할 땐 O(n), 삭제를 할 땐 (O(1)의 시간복잡도를 갖는다.

class PQueue {
  constructor() {
    this.front = null;
    this.rear = null;
  }

  insert(element, priority) {
    let node = new newNode(element, priority);

    if (this.front == null) {
      this.front = node;
      this.rear = node;
    } else {
      let temp = this.front;
      let prev = null;
      while (temp != null && temp.priority <= priority) {
        prev = temp;
        temp = temp.next;
      }
      node.next = temp;
      if (prev != null) prev.next = node;
      else this.front = node;
      if (node.next == null) this.rear = node;
    }
  }

  del() {
    if (this.front == null) console.log("Queue Empty");
    else {
      let temp = this.front;
      console.log("Delementted elementment is: " + temp.data + temp.priority);
      this.front = this.front.next;
      temp = null;
    }
    if (this.front == null) console.log("Now Queue Empty");
  }

  display() {
    let temp = this.front;
    while (temp != null) {
      console.log(temp.data, temp.priority);
      temp = temp.next;
    }
  }
}

class newNode {
  constructor(data, priority, next) {
    this.data = data;
    this.priority = priority;
    this.next = null;
  }
}

const front = new PQueue();
// 데이터와 우선순위를 같이 삽입
front.insert(10, 3);
front.insert(20, 8);
front.insert(30, 5);
front.insert(40, 1);
front.insert(50, 15);
console.log("모두 삽입 후에");
front.display();
/*
display() 결과
40 1
10 3
30 5
20 8
50 15
*/

front.del();
console.log("우선순위가 가장 높은 요소 삭제");
front.display();
/*
display() 결과
10 3
30 5
20 8
50 15
*/
front.del();
console.log("우선순위가 가장 높은 요소 삭제");
front.display();
/*
display() 결과
30 5
20 8
50 15
*/

배열과 마찬가지로 삽입의 위치를 찾기 위해 첫 번재 노드부터 마지막에 저장된 노드까지 순회해야 하는 단점이 있다. 그래서 가장 빠른 시간복잡도를 갖는 힙을 사용한다. 힙을 구현하는 방법도 그리 어렵지 않다.

 

 

힙을 구현하는 표준적인 자료구조는 배열이다.

편의성을 위해 배열의 첫번째 인덱스는 비워둔다.

힙은 완전이진트리의 일종이기 때문에 이진탐색트리의 부모-자식 간 관계와 유사하다.

• 왼쪽 자식의 index = 부모 index * 2
• 오른쪽 자식의 index = (부모 index * 2) + 1
• 부모의 index = Math.floor(자식의 인덱스 / 2)

 

힙 요소 추가

1. 트리의 가장 마지막 노드에 위치한다.
2. 부모 노드보다 우선순위가 높다면 부모 노드와 순서를 바꾼다.
3. 1,2 과정을 반복하면 결국 가장 우선순위가 높은 노드가 된다.
4. 완전 이진 트리의 높이는 log n이므로 시간복잡도는 O(log n)이다.

class MaxHeap {
	constructor() {
		// 0번 인덱스는 편의상 비워둔다.
		this.heap = [null];
	}

	insert(value) {
		this.heap.push(value);
		let currentIndex = this.heap.length - 1;
		let parentIndex = Math.floor(currentIndex / 2);

		// 부모가 추가된 값보다 작을때까지
		while (parentIndex !== 0 && this.heap[parentIndex] < value) {
			const temp = this.heap[parentIndex];
			this.heap[parentIndex] = value;
			this.heap[currentIndex] = temp;

			currentIndex = parentIndex;
			parentIndex = Math.floor(currentIndex / 2);
		}
	}
}

 

힙  요소 제거

1. 요소 제거는 루트 노드만 가능하다.
2. 루트 노드를 제거한 후 가장 마지막 노드가 루트에 위치한다.
3. 루트 노드의 두 자식 노드 중 우선순위가 더 높은 노드와 바꾼다.
4. 두 자식 노드가 우선순위가 더 낮을 때 까지 1,2,3을 반복한다.
5. 완전 이진 트리의 높이는 log n이므로 시간복잡도는 O(log n)이다.

class MaxHeap {
	constructor() {
		// 0번 인덱스는 편의상 비워둔다.
		this.heap = [null];
	}
    
	remove() {
		// 1. 루트요소 반환하기 위해 상수에 임시 저장
		// 2. 가장 마지막 노드가 루트에 위치한다.
		const returnValue = this.heap[1];
		this.heap[1] = this.heap.pop();

		let currentIndex = 1;
		let leftIndex = 2;
		let rightIndex = 3;

		while (
			// 왼쪽,오른쪽 자식 노드들이 현재 노드보다 작을때까지
			this.heap[currentIndex] < this.heap[leftIndex] ||
			this.heap[currentIndex] < this.heap[rightIndex]
		) {
			if (this.heap[leftIndex] < this.heap[rightIndex]) {
				// 오른쪽노드가 왼쪽노드보다 크다면 오른쪽노드와 부모노드를 바꾼다.
				const temp = this.heap[currentIndex];
				this.heap[currentIndex] = this.heap[rightIndex];
				this.heap[rightIndex] = temp;
				currentIndex = rightIndex;
			} else {
				// 아니라면 왼쪽노드와 부모노드를 바꾼다.
				const temp = this.heap[currentIndex];
				this.heap[currentIndex] = this.heap[leftIndex];
				this.heap[leftIndex] = temp;
				currentIndex = leftIndex;
			}
			leftIndex = currentIndex * 2;
			rightIndex = currentIndex * 2 + 1;
		}

		return returnValue;
	}
}

 

정리

정리해보자면, 힙은 우선순위큐를 구현하기 위해 만들어진 자료구조이다.

우선순위 큐(Priority Queue)란 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말한다.

 

배열로 우선순위 큐를 구현

우선순위가 높은 순서대로 배열에 넣는다면 우선순위가 높은 데이터를 반환하는 것은 맨 앞의 인덱스를 이용하면 되므로 어렵지 않다. 하지만 삽입을 하는 과정에선 삽입 위치를 찾기 위해 데이터들을 모두 한칸씩 뒤로 밀어야하고, 최악의 경우 모든 인덱스를 탐색해야하기 때문에 시간 복잡도는 O(n)이다.

 

연결리스트로 우선순위 큐를 구현

연결리스트도 마찬가지로 순위가 높은 순서대로 연결시키면, 우선순위가 높은 데이터 반환은 배열처럼 쉽다. 하지만 연결리스트 또한 삽입 과정에서 삽입 위치를 찾아야하기 때문에 최악의 경우 모든 노드를 탐색해야한다. 마찬가지로 시간복잡도는 O(n)이다.

 

힙으로 우선순위 큐를 구현

힙은 반정렬 상태이고 완전이진트리를 기반으로 만들어졌기 때문에 이진탐색트리의 높이인 O(log n)의 시간복잡도를 갖는다. 

 

힙하다 힙해

---

참고

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