좌경 더미 (효율 적 인 합병 이 가능 한 우선 대기 열)
일반적인 이 진 더미 의 합병 복잡 도 는 O (n) 이 고 좌경 더미 의 합병 복잡 도 는 O (logn) 에 불과 하 다.(그렇지 않 으 면 h1 과 h2 를 교환 합 니 다) h2 의 뿌리 를 합 친 루트 노드 로 하고 merge (h1. root, h2. root. right) 를 재 귀적 으로 호출 합 니 다. 돌아 온 결 과 는 h2. root 의 오른쪽 서브 트 리 입 니 다. merge 작업 으로 돌아 온 트 리 가 왼쪽 경사 트 리 조건 을 만족 시 킬 수 있 기 때문에 돌아 온 결과 (지금 은 h2. root 의 오른쪽 서브 트 리 입 니 다)이미 왼쪽 나무 입 니 다. h2. root. right 의 NPL 값 이 h2. root. left 의 NPL 값 보다 크 면 두 개의 하위 나무 h2. root. left 와 h2. root. right 를 교환 하고 마지막 으로 h2. root 의 NPL 을 업데이트 해 야 합 니 다.
왼쪽 에 있 는 Extract - Min 작업 은 루트 노드 를 삭제 한 다음 merge 작업 을 통 해 좌우 트 리 를 새로운 왼쪽 트 리 로 합 칩 니 다. Insert 작업 은 삽입 할 요 소 를 루트 노드 만 포함 하 는 왼쪽 경사 로 보고 merge 작업 을 통 해 두 개의 왼쪽 경사 로 를 합 칩 니 다.
구조 좌경 로: Insert 작업 을 한다 면 복잡 도 는 O (nlogn) 이 고, 일반 이차 로 의 구조 방법 을 사용한다 면 복잡 도 는 O (n) 이다. 그러나 이것 은 가장 좋 은 좌경 로 가 아니다. 왜냐하면 한편 으로 는 구조의 좌경 로 가 완전 이차 수 이지 만 다른 한편 으로 는 수조 에 따라 조작 할 수 없 기 때문이다. FIFO 대기 열 구 조 를 사용 하면 O (n) 에 도달 할 수 있다.복잡 도, 동시에 구 조 된 좌경 적 좌경 적 효과 가 가장 좋다. 방법 은 다음 과 같다. 각 원 소 를 좌경 적 으로 한다 (두 원소 의 값 이 같 도록 허용 한다)순서대로 enqueue 를 한 다음 에 매번 대열 에서 dequeue 두 개의 좌경 더 미 를 merge 알고리즘 으로 합병 하고 합 병 된 좌경 더 미 를 팀 의 끝 에 놓 습 니 다. 대열 에 좌경 더 미 를 하나 남 길 때 까지 이 좌경 더 미 는 최종 결과 입 니 다.
실현:
import java.util.LinkedList;
/**
*
* Leftist Heap
*
* Copyright (c) 2011 ljs (http://blog.csdn.net/ljsspace/)
* Licensed under GPL (http://www.opensource.org/licenses/gpl-license.php)
*
* @author ljs
* 2011-08-20
*
*/
public class LeftistMinHeap {
static class LeftistHeapNode{
int key;
LeftistHeapNode left;
LeftistHeapNode right;
int npl; //null-path-length
public LeftistHeapNode(int key){
this.key = key;
this.npl = 0;
}
public String toString(){
return this.key + "(npl=" + this.npl + ")";
}
public LeftistHeapNode merge(LeftistHeapNode rhsRoot){
if(rhsRoot==this || rhsRoot == null) return this;
LeftistHeapNode root1 = null; //the root of the merged tree
LeftistHeapNode root2 = null;
if(rhsRoot.key<this.key){
//merge this with rhsRoot's right child
root1 = rhsRoot;
root2 = this;
}else{
//merge rhsRoot with this's right child
root1 = this;
root2 = rhsRoot;
}
LeftistHeapNode tmpRoot = root2.merge(root1.right);
root1.right = tmpRoot;
if(root1.left == null){ //left can not be null unless right is null
root1.right = null;
root1.left = tmpRoot;
root1.npl = 0;
}else{
if(root1.right.npl>root1.left.npl){
//swap left and right child
root1.right = root1.left;
root1.left = tmpRoot;
}
//at this time, the right child has the shortest null-path
root1.npl = root1.right.npl + 1;
}
return root1;
}
}
private LeftistHeapNode root;
public LeftistMinHeap(LeftistHeapNode root){
this.root = root;
}
private static LeftistHeapNode merge(LeftistHeapNode root1,LeftistHeapNode root2){
if(root1 == null) return root2;
if(root2 == null) return root1;
return root1.merge(root2);
}
public static LeftistMinHeap merge(LeftistMinHeap h1,LeftistMinHeap h2){
LeftistHeapNode rootNode = merge(h1.root,h2.root);
return new LeftistMinHeap(rootNode);
}
public static LeftistMinHeap buildHeap(int[] A){
LinkedList<LeftistHeapNode> queue = new LinkedList<LeftistHeapNode>();
int n = A.length;
//init: queue all elements as a single-node tree
for(int i=0;i<n;i++){
LeftistHeapNode node = new LeftistHeapNode(A[i]);
queue.add(node);
}
//merge adjacent heaps and enqueue the merged heap afterward
while(queue.size()>1){
LeftistHeapNode root1 = queue.remove(); //dequeue
LeftistHeapNode root2 = queue.remove();
LeftistHeapNode rootNode = merge(root1,root2);
queue.add(rootNode);
}
LeftistHeapNode rootNode = queue.remove();
return new LeftistMinHeap(rootNode);
}
public void insert(int x){
this.root = LeftistMinHeap.merge(new LeftistHeapNode(x), this.root);
}
public Integer extractMin(){
if(this.root == null) return null;
int min = this.root.key;
this.root = LeftistMinHeap.merge(this.root.left, this.root.right);
return min;
}
public static void main(String[] args) {
int[] A = new int[]{4,8,10,9,1,3,5,6,11};
LeftistMinHeap heap = LeftistMinHeap.buildHeap(A);
heap.insert(7);
Integer min = null;
while((min = heap.extractMin()) != null){
System.out.format(" %d", min);
}
System.out.println();
System.out.println("********************");
A = new int[]{3,10,8,21,14,17,23,26};
LeftistHeapNode a0 = new LeftistHeapNode(A[0]);
LeftistHeapNode a1 = new LeftistHeapNode(A[1]);
LeftistHeapNode a2 = new LeftistHeapNode(A[2]);
LeftistHeapNode a3 = new LeftistHeapNode(A[3]);
LeftistHeapNode a4 = new LeftistHeapNode(A[4]);
LeftistHeapNode a5 = new LeftistHeapNode(A[5]);
LeftistHeapNode a6 = new LeftistHeapNode(A[6]);
LeftistHeapNode a7 = new LeftistHeapNode(A[7]);
a0.left = a1; a0.npl = 1;
a0.right = a2;
a1.left = a3; a1.npl = 1;
a1.right = a4;
a4.left = a6;
a2.left = a5;
a5.left = a7;
LeftistMinHeap h1 = new LeftistMinHeap(a0);
int[] B = new int[]{6,12,7,18,24,37,18,33};
LeftistHeapNode b0 = new LeftistHeapNode(B[0]);
LeftistHeapNode b1 = new LeftistHeapNode(B[1]);
LeftistHeapNode b2 = new LeftistHeapNode(B[2]);
LeftistHeapNode b3 = new LeftistHeapNode(B[3]);
LeftistHeapNode b4 = new LeftistHeapNode(B[4]);
LeftistHeapNode b5 = new LeftistHeapNode(B[5]);
LeftistHeapNode b6 = new LeftistHeapNode(B[6]);
LeftistHeapNode b7 = new LeftistHeapNode(B[7]);
b0.left = b1; b0.npl = 2;
b0.right = b2;
b1.left = b3; b1.npl = 1;
b1.right = b4;
b4.left = b7;
b2.left = b5; b2.npl = 1;
b2.right = b6;
LeftistMinHeap h2 = new LeftistMinHeap(b0);
heap = LeftistMinHeap.merge(h1,h2);
while((min = heap.extractMin()) != null){
System.out.format(" %d", min);
}
System.out.println();
System.out.println("********************");
A = new int[]{1,5,7,10,15,20,25,50,99};
a0 = new LeftistHeapNode(A[0]);
a1 = new LeftistHeapNode(A[1]);
a2 = new LeftistHeapNode(A[2]);
a3 = new LeftistHeapNode(A[3]);
a4 = new LeftistHeapNode(A[4]);
a5 = new LeftistHeapNode(A[5]);
a6 = new LeftistHeapNode(A[6]);
a7 = new LeftistHeapNode(A[7]);
LeftistHeapNode a8 = new LeftistHeapNode(A[8]);
a0.left = a1; a0.npl = 2;
a0.right = a2;
a1.left = a3; a1.npl = 1;
a1.right = a4;
a2.left = a5; a2.npl = 1;
a2.right = a6;
a5.left = a7; a5.npl = 1;
a5.right = a8;
h1 = new LeftistMinHeap(a0);
B = new int[]{22,75};
b0 = new LeftistHeapNode(B[0]);
b1 = new LeftistHeapNode(B[1]);
b0.left = b1;
h2 = new LeftistMinHeap(b0);
heap = LeftistMinHeap.merge(h1,h2);
while((min = heap.extractMin()) != null){
System.out.format(" %d", min);
}
System.out.println();
}
}
테스트 출력:
1 3 4 5 6 7 8 9 10 11
********************
3 6 7 8 10 12 14 17 18 18 21 23 24 26 33 37
********************
1 5 7 10 15 20 22 25 50 75 99
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
