最小堆的基础操作(Java)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了最小堆的基础操作(Java)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1737字，纯文字阅读大概需要3分钟。

内容图文

 1 public class test
 2 {
 3     public static void main(String[] args)
 4     {
 5         int[] array = new int[] {3,5,6,11,20,8,9,2,7};
 6         createMinimumHeap(array);
 7         for(int value : array)
 8             System.out.print(value + " ");
 9         System.out.println();
10         for(int i = 0; i < array.length; i++)
11             System.out.print(extract_Min(array, array.length - i) + " ");
12     }
13     
14     //1 建堆
15     public static void createMinimumHeap(int[] array)
16     {
17         int k = array.length / 2 - 1;
18         while(k >= 0)
19         {
20             Min_Heapify(array, k, array.length);
21             k -= 1;
22         }
23     }
24 
25     //2 最小堆化
26     public static void Min_Heapify(int[] array, int k, int size)
27     {
28         int min_index;
29         while(k <= size / 2 - 1)
30         {
31             if(k * 2 + 2 >= size)
32                 min_index = k * 2 + 1;
33             else
34                 min_index = array[k * 2 + 1] < array[k * 2 + 2] ? k * 2 + 1 : k * 2 + 2;
35             if(array[k] > array[min_index])
36             {
37                 swap(array, k, min_index);
38                 k = min_index;
39             }
40             else
41                 break;
42         }
43     }
44 
45     //3 提取最小元素
46     public static int extract_Min(int[] array, int size)
47     {
48         int key = array[0];
49         array[0] = array[size - 1];
50         //最小堆化
51         Min_Heapify(array, 0, size - 1);
52         return key;
53     }
54     
55     //4 插入元素
56     //将插入的元素放在数组最后 依次与其父亲结点进行比较 直到根结点
57     
58     public static void swap(int[] a, int i, int j)
59     {
60         int tmp = a[i];
61         a[i] = a[j];
62         a[j] = tmp;
63     }
64 }

内容总结

以上是互联网集市为您收集整理的最小堆的基础操作(Java)全部内容，希望文章能够帮你解决最小堆的基础操作(Java)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端