ㅏ 최소 힙 각 내부 노드의 값이 해당 노드의 하위 노드 값보다 작거나 같은 완전 이진 트리입니다.
힙의 요소를 배열로 매핑하는 것은 간단합니다. 노드가 인덱스에 저장된 경우 케이 , 그럼 그거야 왼쪽 아이 인덱스에 저장됩니다 2k+1 그리고 그것의 오른쪽 아이 색인에서 2k+2 ~을 위한 0 기반 인덱싱 그리고 1 기반 인덱싱 왼쪽 아이는 2천 그리고 오른쪽 아이는 에 있을 거예요 2k+1 .
최소 힙의 예:
5 13 / / 10 15 16 31 / / / 30 41 51 100 41>
Min Heap은 어떻게 표현되나요?
최소 힙은 완전한 이진 트리입니다. 최소 힙은 일반적으로 배열로 표시됩니다. 루트 요소는 다음 위치에 있습니다. 도착[0] . 임의의 i번째 노드에 대해, 즉, 도착[i] :
- Arr[(i -1) / 2]는 상위 노드를 반환합니다. Arr[(2 * i) + 1]은 왼쪽 자식 노드를 반환합니다. Arr[(2 * i) + 2]는 오른쪽 자식 노드를 반환합니다.
최소 힙 작업:
- getMin() : Min Heap의 루트 요소를 반환합니다. 이 작업의 시간 복잡도는 오(1) . extractMin() : MinHeap에서 최소 요소를 제거합니다. 이 작업의 시간 복잡도는 O(로그n) 이 작업은 루트를 제거한 후 (heapify()를 호출하여) 힙 속성을 유지해야 하기 때문입니다. insert() : 새 키를 삽입하려면 다음이 필요합니다. O(로그n) 시간. 트리 끝에 새 키를 추가합니다. 새 키가 상위 키보다 크면 아무 작업도 수행할 필요가 없습니다. 그렇지 않으면 위반된 힙 속성을 수정하기 위해 위로 순회해야 합니다.
다음은 Python에서 Min Heap을 구현한 것입니다.
스크립트를 실행 가능하게 만들기
파이썬3
# Python3 implementation of Min Heap> > import> sys> > class> MinHeap:> > >def> __init__(>self>, maxsize):> >self>.maxsize>=> maxsize> >self>.size>=> 0> >self>.Heap>=> [>0>]>*>(>self>.maxsize>+> 1>)> >self>.Heap[>0>]>=> ->1> *> sys.maxsize> >self>.FRONT>=> 1> > ># Function to return the position of> ># parent for the node currently> ># at pos> >def> parent(>self>, pos):> >return> pos>/>/>2> > ># Function to return the position of> ># the left child for the node currently> ># at pos> >def> leftChild(>self>, pos):> >return> 2> *> pos> > ># Function to return the position of> ># the right child for the node currently> ># at pos> >def> rightChild(>self>, pos):> >return> (>2> *> pos)>+> 1> > ># Function that returns true if the passed> ># node is a leaf node> >def> isLeaf(>self>, pos):> >return> pos>*>2> >>self>.size> > ># Function to swap two nodes of the heap> >def> swap(>self>, fpos, spos):> >self>.Heap[fpos],>self>.Heap[spos]>=> self>.Heap[spos],>self>.Heap[fpos]> > ># Function to heapify the node at pos> >def> minHeapify(>self>, pos):> > ># If the node is a non-leaf node and greater> ># than any of its child> >if> not> self>.isLeaf(pos):> >if> (>self>.Heap[pos]>>self>.Heap[>self>.leftChild(pos)]>or> >self>.Heap[pos]>>self>.Heap[>self>.rightChild(pos)]):> > ># Swap with the left child and heapify> ># the left child> >if> self>.Heap[>self>.leftChild(pos)] <>self>.Heap[>self>.rightChild(pos)]:> >self>.swap(pos,>self>.leftChild(pos))> >self>.minHeapify(>self>.leftChild(pos))> > ># Swap with the right child and heapify> ># the right child> >else>:> >self>.swap(pos,>self>.rightChild(pos))> >self>.minHeapify(>self>.rightChild(pos))> > ># Function to insert a node into the heap> >def> insert(>self>, element):> >if> self>.size>>=> self>.maxsize :> >return> >self>.size>+>=> 1> >self>.Heap[>self>.size]>=> element> > >current>=> self>.size> > >while> self>.Heap[current] <>self>.Heap[>self>.parent(current)]:> >self>.swap(current,>self>.parent(current))> >current>=> self>.parent(current)> > ># Function to print the contents of the heap> >def> Print>(>self>):> >for> i>in> range>(>1>, (>self>.size>/>/>2>)>+>1>):> >print>(>' PARENT : '>+> str>(>self>.Heap[i])>+>' LEFT CHILD : '>+> >str>(>self>.Heap[>2> *> i])>+>' RIGHT CHILD : '>+> >str>(>self>.Heap[>2> *> i>+> 1>]))> > ># Function to build the min heap using> ># the minHeapify function> >def> minHeap(>self>):> > >for> pos>in> range>(>self>.size>/>/>2>,>0>,>->1>):> >self>.minHeapify(pos)> > ># Function to remove and return the minimum> ># element from the heap> >def> remove(>self>):> > >popped>=> self>.Heap[>self>.FRONT]> >self>.Heap[>self>.FRONT]>=> self>.Heap[>self>.size]> >self>.size>->=> 1> >self>.minHeapify(>self>.FRONT)> >return> popped> > # Driver Code> if> __name__>=>=> '__main__'>:> > >print>(>'The minHeap is '>)> >minHeap>=> MinHeap(>15>)> >minHeap.insert(>5>)> >minHeap.insert(>3>)> >minHeap.insert(>17>)> >minHeap.insert(>10>)> >minHeap.insert(>84>)> >minHeap.insert(>19>)> >minHeap.insert(>6>)> >minHeap.insert(>22>)> >minHeap.insert(>9>)> >minHeap.minHeap()> > >minHeap.>Print>()> >print>(>'The Min val is '> +> str>(minHeap.remove()))> |
선택 정렬
>
>
출력 :
The Min Heap is PARENT : 3 LEFT CHILD : 5 RIGHT CHILD :6 PARENT : 5 LEFT CHILD : 9 RIGHT CHILD :84 PARENT : 6 LEFT CHILD : 19 RIGHT CHILD :17 PARENT : 9 LEFT CHILD : 22 RIGHT CHILD :10 The Min val is 3>
라이브러리 기능 사용:
우리는 사용 힙 Python에서 Heap을 구현하는 클래스입니다. 기본적으로 최소 힙은 이 클래스에 의해 구현됩니다.
자식 모두 추가
파이썬3
# Python3 program to demonstrate working of heapq> > from> heapq>import> heapify, heappush, heappop> > # Creating empty heap> heap>=> []> heapify(heap)> > # Adding items to the heap using heappush function> heappush(heap,>10>)> heappush(heap,>30>)> heappush(heap,>20>)> heappush(heap,>400>)> > # printing the value of minimum element> print>(>'Head value of heap : '>+>str>(heap[>0>]))> > # printing the elements of the heap> print>(>'The heap elements : '>)> for> i>in> heap:> >print>(i, end>=> ' '>)> print>(>'
'>)> > element>=> heappop(heap)> > # printing the elements of the heap> print>(>'The heap elements : '>)> for> i>in> heap:> >print>(i, end>=> ' '>)> |
Java에서 json에 대한 객체
>
>
출력 :
Head value of heap : 10 The heap elements : 10 30 20 400 The heap elements : 20 30 400>