左式堆合并的时间复杂度为O(N) , 由于n个节点的左式堆的右子树最多含有log(N+1)个节点, 而且每次合并都是与较小值堆的右子树进行比较, 所以为O(N).
1 package heap; 2 3 import java.util.LinkedList; 4 import java.util.Queue; 5 import java.util.Stack; 6 7 public class LeftHeap 8 { 9 int num ; 10 LeftHeap left ; 11 LeftHeap right ; 12 int npl ; 13 14 public LeftHeap() {} 15 16 public LeftHeap(int num, int npl) { 17 this.npl = npl; 18 this.num = num; 19 } 20 21 public static LeftHeap create1(int[] num) 22 { 23 if(num == null || num.length < 1) 24 return null ; 25 Queue<LeftHeap> queue = new LinkedList<>() ; 26 for(int i=0 ; i<num.length ; i++) 27 { 28 queue.add(new LeftHeap(num[i] , 0)) ; 29 } 30 31 while (queue.size()>=2) 32 { 33 LeftHeap h1 = queue.poll() ; 34 LeftHeap h2 = queue.poll() ; 35 36 LeftHeap heap = merge(h1 , h2) ; 37 queue.add(heap) ; 38 } 39 40 return queue.poll() ; 41 } 42 43 public static LeftHeap create2(int[] num) 44 { 45 if(num == null || num.length < 1) 46 return null ; 47 int N = num.length ; 48 LeftHeap[] arr = new LeftHeap[N+1] ; 49 for(int i=0 ; i<N ; i++) 50 { 51 arr[i+1] = new LeftHeap(num[i] , 0) ; 52 } 53 54 for(int k=N/2 ; k>=1 ; k--) 55 sink(arr , k , N) ; 56 return arr[1] ; 57 } 58 59 private static void sink(LeftHeap[] heap , int k , int N) 60 { 61 while (k*2 <= N) 62 { 63 int min = k*2 ; 64 heap[k].left = heap[min] ; 65 if(min+1 <= N) 66 { 67 heap[k].right = heap[min+1] ; 68 heap[k].npl = heap[min+1].npl+1 ; 69 if(heap[min].num > heap[min+1].num) 70 min++ ; 71 } 72 73 if(heap[k].num > heap[min].num) 74 { 75 int temp = heap[k].num ; 76 heap[k].num = heap[min].num ; 77 heap[min].num = temp ; 78 k=min ; 79 } 80 else 81 break ; 82 } 83 } 84 85 public static LeftHeap insert(int num , LeftHeap h1) 86 { 87 LeftHeap h = new LeftHeap(num , 0) ; 88 return merge_unrec(h1 , h) ; 89 } 90 91 public static LeftHeap deleteMin(LeftHeap h) 92 { 93 if(h == null) 94 return null ; 95 return merge_unrec(h.left , h.right) ; 96 } 97 98 /** 99 * 左式堆合并的非递归实现 100 */ 101 public static LeftHeap merge_unrec(LeftHeap h1 , LeftHeap h2) 102 { 103 if(h1 == null || h2 == null) 104 return h1 == null ? h2 : h1 ; 105 106 Stack<LeftHeap> stack = new Stack<>() ; //用于保存每一级的父节点 107 108 while (h2 != null || !stack.isEmpty()) 109 { 110 if(h1 != null && h2 != null) 111 { 112 if(h1.num > h2.num) //确保h1为小值的堆,h2为大值的堆 113 { 114 LeftHeap temp = h1 ; 115 h1 = h2 ; 116 h2 = temp ; 117 } 118 119 if(h1.left == null) //当小堆的左子树为空时, 直接将h2作为他的左子树即可, 由于仍不存在右子树, 所以npl无需更新 120 { 121 h1.left = h2 ; 122 h2 = null ; 123 } 124 else 125 { 126 stack.push(h1) ; //说明左右子树都存在, 此时应将h1保存, 让h1的右子树和h2进行合并 127 h1 = h1.right ; 128 } 129 } 130 else //各级的父节点连接右子树 131 { 132 if(h1 == null) 133 { 134 h1 = h2 ; 135 h2 = null ; 136 } 137 while (!stack.isEmpty()) 138 { 139 LeftHeap heap = stack.pop() ; 140 heap.right = h1 ; 141 if(heap.left.npl < heap.right.npl) 142 swapLR(heap) ; 143 heap.npl = heap.right.npl+1 ; 144 h1 = heap ; 145 } 146 } 147 } 148 return h1 ; 149 } 150 151 public static LeftHeap merge(LeftHeap h1 , LeftHeap h2) 152 { 153 if(h1 == null || h2 == null) 154 return h1 == null ? h2 : h1 ; 155 if(h1.num > h2.num) 156 return merge1(h2 , h1) ; 157 else 158 return merge1(h1 , h2) ; 159 } 160 161 private static LeftHeap merge1(LeftHeap h1 , LeftHeap h2) 162 { 163 if(h1.left == null) 164 h1.left = h2 ; 165 else 166 { 167 h1.right = merge(h1.right , h2) ; 168 if(h1.left.npl < h1.right.npl) 169 swapLR(h1) ; 170 h1.npl = h1.right.npl+1 ; 171 } 172 173 return h1 ; 174 } 175 176 private static void swapLR(LeftHeap h) 177 { 178 LeftHeap temp = h.left ; 179 h.left = h.right ; 180 h.right = temp ; 181 } 182 183 public static void inOrder(LeftHeap heap) 184 { 185 if(heap == null) 186 return ; 187 inOrder(heap.left); 188 System.out.print(heap.num + " "); 189 inOrder(heap.right); 190 } 191 public static void main(String[] args) 192 { 193 int[] arr = new int[]{ 194 6,2,8,11,22,3 195 } ; 196 LeftHeap heap = create1(arr) ; 197 inOrder(heap); 198 /*LeftHeap h1 = new LeftHeap(3, 1) ; 199 LeftHeap h2 = new LeftHeap(10, 1) ; 200 LeftHeap h3 = new LeftHeap(8, 0) ; 201 LeftHeap h4 = new LeftHeap(21, 0) ; 202 LeftHeap h5 = new LeftHeap(14, 0) ; 203 LeftHeap h6 = new LeftHeap(17, 0) ; 204 LeftHeap h7 = new LeftHeap(23, 0) ; 205 LeftHeap h8 = new LeftHeap(26, 0) ; 206 207 h1.left = h2 ; 208 h1.right = h3 ; 209 h2.left = h4 ; 210 h2.right = h5 ; 211 h3.left = h6 ; 212 h5.left = h7 ; 213 h6.left = h8 ; 214 215 LeftHeap a = h1 ; 216 217 h1 = new LeftHeap(6,2) ; 218 h2 = new LeftHeap(12,1) ; 219 h3 = new LeftHeap(7,1) ; 220 h4 = new LeftHeap(18,0) ; 221 h5 = new LeftHeap(24,0) ; 222 h6 = new LeftHeap(37,0) ; 223 h7 = new LeftHeap(18,0) ; 224 h8 = new LeftHeap(33,0) ; 225 226 h1.left = h2 ; 227 h1.right = h3 ; 228 h2.left = h4 ; 229 h2.right = h5 ; 230 h3.left = h6 ; 231 h3.right = h7 ; 232 h5.left = h8 ; 233 234 LeftHeap b = h1 ; 235 236 LeftHeap heap = merge_unrec(a , b) ; 237 238 inOrder(heap) ;*/ 239 240 } 241 }