第6章 堆排序 java实现 简单版 泛型版 最大优先级队列

方案一、只考虑int类型的排序，最简单的实现如下。

 1 public class Heap {
 2     
 3     public int heap_size;//在build_max_heap中初始化，由heap_sort自动调用
 4     
 5     public int parent(int i){
 6         return (i - 1) / 2;
 7     }
 8     public int left(int i){
 9         return 2 * i + 1;
10     }
11     public int right(int i){
12         return 2 * i + 2;
13     }
14     
15     /** 保持堆的性质,
16      * 假定left(i), right(i)为根的两根二叉树都是最大堆，
17      * A[i]可能小于其子女，这样就违背了最大堆性质
18      * 该函数让A[i]在最大堆中“下降”，使以i为根的子树成为最大堆
19      * */
20     public void max_heapify(int[] A, int i){
21         int l = left(i);
22         int r = right(i);
23         int largest;
24         // 从A[i] A[left(i)] A[right(i)] 中找出最大，下标存在largest中
25         // 若A[i]为最大，则根据假设，i为根的子树已是最大堆，函数结束
26         // 否则交换A[i]和A[largest],交换后下标为largest的节点值为A[i]
27         // 该节点的子树可能违反最大堆,因此对largest下标递归调用
28         if(l < heap_size && A[l] > A[i]){
29             largest = l;
30         } 
31         else{
32             largest = i;
33         }    
34         if(r < heap_size && A[r] > A[largest]){
35             largest = r;
36         }
37         if(largest != i){
38             int tmp = A[i];
39             A[i] = A[largest];
40             A[largest] = tmp;
41             
42             max_heapify(A, largest);
43         }
44     }
45     
46     /**
47      * 建堆
48      * 自底向上将数组A[1..n]（此处n=length[A]）变成最大堆
49      * 子数组A[(floor(n / 2) + 1) .. n]中的元素都是树中的叶子
50      * 所以对每一个非叶子节点都调用一次该过程
51      * */
52     public void build_max_heap(int[] A){
53         heap_size = A.length; // 初始化heap_size
54         for(int i = (heap_size/2 - 1); i > -1; --i){
55             max_heapify(A, i);
56         }
57     }
58     
59     /**
60      * 堆排序算法
61      * 先建造最大堆，根A[1]即为最大，则置换到数组的正确位置A[n]
62      * 从堆中去掉节点n，A[1..n-1]建成最大堆，但新根可能违背了最大堆性质，
63      * 此时调用max_heapify(A,1)可以保持该性质，在A[1..n-1]构造出最大堆。
64      * 不断重复，堆大小从n-1降到2
65      * */
66     public void heapsort(int[] A){
67         build_max_heap(A);
68         for(int i = A.length-1; i > 0; --i){
69             int tmp = A[0];
70             A[0] = A[i];
71             A[i] = tmp;
72             --heap_size;
73             max_heapify(A, 0);
74         }
75     }
76     
77     public static void show_array(int[] A){
78         for(int i = 0; i < A.length; ++i){
79             System.out.print(A[i] + ". ");
80         }
81         System.out.println();
82     }
83     
84     public static void main(String[] args){
85         int[] A = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
86         
87         
88         System.out.println("before heapsort：");
89         show_array(A);
90         
91         Heap h = new Heap();
92         h.heapsort(A);
93         
94         System.out.println("after heapsort：");
95         show_array(A);
96         
97     }
98     
99 }

 运行结果：

方案二、考虑泛型，使用泛型数组的实现如下：

  1 public class HeapTwo<T extends Comparable<T>> {
  2     
  3     T[] A;
  4     int heap_size;//在build_max_heap中初始化，由heap_sort自动调用，或在类实例化时构造
  5     
  6     public HeapTwo(T[] A){
  7         this.A = A;
  8         this.heap_size = A.length;
  9     }
 10     
 11     public int parent(int i){
 12         return (i - 1) / 2;
 13     }
 14     public int left(int i){
 15         return 2 * i + 1;
 16     }
 17     public int right(int i){
 18         return 2 * i + 2;
 19     }
 20     
 21     /** 保持堆的性质,
 22      * 假定left(i), right(i)为根的两根二叉树都是最大堆，
 23      * A[i]可能小于其子女，这样就违背了最大堆性质
 24      * 该函数让A[i]在最大堆中“下降”，使以i为根的子树成为最大堆
 25      * */
 26     public void max_heapify(int i){
 27         int l = left(i);
 28         int r = right(i);
 29         int largest;
 30         // 从A[i] A[left(i)] A[right(i)] 中找出最大，下标存在largest中
 31         // 若A[i]为最大，则根据假设，i为根的子树已是最大堆，函数结束
 32         // 否则交换A[i]和A[largest],交换后下标为largest的节点值为A[i]
 33         // 该节点的子树可能违反最大堆,因此对largest下标递归调用
 34         if(l < heap_size && A[l].compareTo(A[i]) > 0 ){
 35             largest = l;
 36         } 
 37         else{
 38             largest = i;
 39         }    
 40         if(r < heap_size && A[r].compareTo(A[largest]) > 0){
 41             largest = r;
 42         }
 43         if(largest != i){
 44             T tmp = A[i];
 45             A[i] = A[largest];
 46             A[largest] = tmp;
 47             
 48             max_heapify(largest);
 49         }
 50     }
 51     
 52     /**
 53      * 建堆
 54      * 自底向上将数组A[1..n]（此处n=length[A]）变成最大堆
 55      * 子数组A[(floor(n / 2) + 1) .. n]中的元素都是树中的叶子
 56      * 所以对每一个非叶子节点都调用一次该过程
 57      * */
 58     public void build_max_heap(){
 59         heap_size = A.length; // 初始化heap_size
 60         for(int i = (heap_size/2 - 1); i > -1; --i){
 61             max_heapify(i);
 62         }
 63     }
 64     
 65     /**
 66      * 堆排序算法
 67      * 先建造最大堆，根A[1]即为最大，则置换到数组的正确位置A[n]
 68      * 从堆中去掉节点n，A[1..n-1]建成最大堆，但新根可能违背了最大堆性质，
 69      * 此时调用max_heapify(A,1)可以保持该性质，在A[1..n-1]构造出最大堆。
 70      * 不断重复，堆大小从n-1降到2
 71      * */
 72     public void heapsort(){
 73         build_max_heap();
 74         for(int i = A.length-1; i > 0; --i){
 75             T tmp = A[0];
 76             A[0] = A[i];
 77             A[i] = tmp;
 78             --heap_size;
 79             max_heapify(0);
 80         }
 81     }
 82     
 83     public void show_array(){
 84         for(int i = 0; i < A.length; ++i){
 85             System.out.print(A[i] + ". ");
 86         }
 87         System.out.println();
 88     }
 89     
 90     public static void main(String[] args){
 91         Double[] A = {4.3, 1.2, 3.2, 2.8, 16.5, 9.3, 10.6, 14.6, 8.4, 7.0};
 92         
 93         System.out.println("before heapsort：");
 94         
 95         
 96         HeapTwo h = new HeapTwo(A);
 97         h.show_array();
 98         h.heapsort();
 99         
100         System.out.println("after heapsort：");
101         h.show_array();
102         
103     }
104 }

 最大优先级队列：

  1 package org.hhj;
  2 
  3 public class Heap {
  4     
  5     int[] A;
  6     int heap_size;//在build_max_heap中初始化，由heap_sort自动调用，或在类实例化时构造
  7     
  8     public Heap(int[] A){
  9         this.A = A;
 10         this.heap_size = A.length;
 11     }
 12     
 13     public int parent(int i){
 14         return (i - 1) / 2;
 15     }
 16     public int left(int i){
 17         return 2 * i + 1;
 18     }
 19     public int right(int i){
 20         return 2 * i + 2;
 21     }
 22     
 23     /** 保持堆的性质,
 24      * 假定left(i), right(i)为根的两根二叉树都是最大堆，
 25      * A[i]可能小于其子女，这样就违背了最大堆性质
 26      * 该函数让A[i]在最大堆中“下降”，使以i为根的子树成为最大堆
 27      * */
 28     public void max_heapify(int[] A, int i){
 29         int l = left(i);
 30         int r = right(i);
 31         int largest;
 32         // 从A[i] A[left(i)] A[right(i)] 中找出最大，下标存在largest中
 33         // 若A[i]为最大，则根据假设，i为根的子树已是最大堆，函数结束
 34         // 否则交换A[i]和A[largest],交换后下标为largest的节点值为A[i]
 35         // 该节点的子树可能违反最大堆,因此对largest下标递归调用
 36         if(l < heap_size && A[l] > A[i]){
 37             largest = l;
 38         } 
 39         else{
 40             largest = i;
 41         }    
 42         if(r < heap_size && A[r] > A[largest]){
 43             largest = r;
 44         }
 45         if(largest != i){
 46             int tmp = A[i];
 47             A[i] = A[largest];
 48             A[largest] = tmp;
 49             
 50             max_heapify(A, largest);
 51         }
 52     }
 53     
 54     /**
 55      * 建堆
 56      * 自底向上将数组A[1..n]（此处n=length[A]）变成最大堆
 57      * 子数组A[(floor(n / 2) + 1) .. n]中的元素都是树中的叶子
 58      * 所以对每一个非叶子节点都调用一次该过程
 59      * */
 60     public void build_max_heap(int[] A){
 61         heap_size = A.length; // 初始化heap_size
 62         for(int i = (heap_size/2 - 1); i > -1; --i){
 63             max_heapify(A, i);
 64         }
 65     }
 66     
 67     /**
 68      * 堆排序算法
 69      * 先建造最大堆，根A[1]即为最大，则置换到数组的正确位置A[n]
 70      * 从堆中去掉节点n，A[1..n-1]建成最大堆，但新根可能违背了最大堆性质，
 71      * 此时调用max_heapify(A,1)可以保持该性质，在A[1..n-1]构造出最大堆。
 72      * 不断重复，堆大小从n-1降到2
 73      * */
 74     public void heapsort(int[] A){
 75         build_max_heap(A);
 76         for(int i = A.length-1; i > 0; --i){
 77             int tmp = A[0];
 78             A[0] = A[i];
 79             A[i] = tmp;
 80             --heap_size;
 81             max_heapify(A, 0);
 82         }
 83     }
 84     
 85     public static void show_array(int[] A){
 86         for(int i = 0; i < A.length; ++i){
 87             System.out.print(A[i] + ". ");
 88         }
 89         System.out.println();
 90     }
 91     
 92     /**
 93      * 返回A[]中具有最大关键字的元素
 94      * @param A
 95      * @return
 96      */
 97     public int heap_maximum(int[] A){
 98         return A[0];
 99     }
100     
101     /**
102      * 去掉并返回A中的具有最大关键字的元素
103      * @param A
104      * @return
105      */
106     public int heap_extract_max(int[] A){
107         if(heap_size < 1){
108             System.out.println("heap underflow");
109             return -1;
110         }
111         int max = A[0];
112         A[0] = A[heap_size - 1];
113         --heap_size;
114         max_heapify(A, 0);
115         return max;
116     }
117     
118     /**
119      * 将元素i的关键字的值增加到key，这里key值不可小于i的原关键字的值
120      * @param A
121      * @param i
122      * @param key
123      */
124     public void heap_increase_key(int[] A, int i, int key){
125         if(key < A[i]){
126             System.out.println("new key is smaller than current key");
127         }
128         A[i] = key;
129         while(i > 1 && A[parent(i)] < A[i]){
130             int tmp = A[i];
131             A[i] = A[parent(i)];
132             A[parent(i)] = tmp;
133             i = parent(i);
134         }
135     }
136     
137     /**
138      * 将key插入到最大堆A中，先用一个关键字值为负无穷的叶节点扩展对大队，
139      * 然后调用heap_increase_key来设置新节点的关键字的正确值，并保持最大堆性质。
140      * @param A
141      * @param key
142      */
143     public void max_heap_insert(int[] A, int key){
144         ++heap_size;
145         A[heap_size] = Integer.MIN_VALUE;
146         heap_increase_key(A, heap_size, key);
147         
148     }
149     public static void main(String[] args){
150         
151         
152     }
153     
154 }
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/tobebrave/p/4875521.html