[자료구조]Heap

1. 정의

완전 이진 트리의 일종으로 우선순위 큐를 위해서 만들어진 자료구조

 

2. 특징

MaxHeap : Root 노드가 가장 큰 숫자

MinHeap : Root 노드가 가장 작은 숫자

여러개의 값들 중에서 최대값이나 최소값을 빠르게 찾아낼 수 있다.

중복 값을 허용한다.

자료구조의 힙와 메모리 영역의 힙은 다른 개념이다.

 

3. 구현

1) 삽입(maxheap인 경우)

이진 트리의 맨 아래에 삽입할 값을 넣는다. 부모와 값을 비교하여 교환한다. 더 이상 크지 않을 때까지 반복(MaxHeap인 경우)

        private List<int> A = new List<int>();

        private void Swap(int i, int j)
        {
            int t = A[i];
            A[i] = A[j];
            A[j] = t;
        }
        public void Add(int value)
        {
            A.Add(value);

            int i = A.Count - 1;
            while (i > 0)
            {
                int parent = (i - 1) / 2;
                if(A[parent] < A[i])
                {
                    Swap(parent, i);
                    i = parent;
                }//max hip이란 부모 노드가 항상 크다
                else
                {
                    break;
                }
            }
        }

 

 

 

2) 삭제(maxheap인 경우)

Root node를 삭제한다.

맨 말단 노드와 Root 노드를 교환 후 말단 노드(삭제하려던 원래 Root 노드)를 삭제해준다.

부모와 비교하여 부모가 더 큰 경우 교환한다.

부모보다 작거나, 루트 노드와 이미 비교가 끝난 경우 반복문 중단

public int RemoveOne()
        {
            if (A.Count == 0)
                throw new InvalidOperationException();
            int root = A[0];
            A[0] = A[A.Count - 1];
            A.RemoveAt(A.Count - 1);

            int i = 0;
            int last = A.Count - 1;
            while (i < last)
            {
                int child = i * 2 + 1;

                if(child < last && A[child] < A[child + 1])
                {
                    child = child + 1;
                }
                if (child > last || A[i] >= A[child])
                {
                    break;
                }

                Swap(i, child);
                i = child;
            }
            return root;
        }

 

 

 

 

출처: www.csharpstudy.com/DS/heap.aspx