本文主要是介绍HeapSort and PriorityQueue(堆排序算法和优先队列Java代码实现)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
HeapSort
package Search;
//堆排序算法实现
public class HeapSort {
public static void main(String[] args) {int arr[] = { 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };HeapSort hs = new HeapSort();System.out.print("初始堆：");hs.Print(arr);System.out.println();System.out.print("建堆：");hs.BuildMaxHeap(arr);hs.Print(arr);System.out.println();System.out.print("排序后：");hs.Heap_Sort(arr);hs.Print(arr);}public HeapSort(){}
public HeapSort(int arr[]) {BuildMaxHeap(arr);
}public int heapsize;// 节点i的父亲节点是i/2
public int Parent(int i) {return i / 2;
}// 节点i的左孩子2i
public int Left(int i) {return (2 * i) + 1;
}// 节点i的右孩子2i+1
public int Right(int i) {return (2 * i) + 2;
}// 维护堆的性质，使之永远保持是一个最大堆
public void MaxHeapify(int arr[], int i) {// 记录最大的节点，使之放在根节点int l, r, largest = 0;l = Left(i);r = Right(i);if (l <= heapsize-1 && arr[l] > arr[i]) {largest = l;} else {largest = i;}if (r <= heapsize-1 && arr[r] > arr[largest]) {largest = r;}if (largest != i) {int temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;this.MaxHeapify(arr, largest);}}// 维护堆的性质，使之永远保持是一个最小堆
// public void MinHeapify(int arr[], int i) {
// int smallestest,l,r = 0;//记录最小的节点，使之放在根节点
// l = Left(i);
// r = Right(i);
// if (l <= heapsize-1 && arr[l] <arr[i]) {
// smallestest = l;
// } else
// smallestest = i;
// if (r <= heapsize-1 && arr[r] < arr[smallestest]) {
// smallestest = r;
// }
// if (smallestest != i) {
// int temp = arr[i];
// arr[i] = arr[smallestest];
// arr[smallestest] = temp;
// MaxHeapify(arr,smallestest);
// //MinHeapify(arr,smallestest);
// }
//
// }
// 建堆
public void BuildMaxHeap(int arr[]) {
this.heapsize = arr.length;
for (int i = (arr.length - 1) / 2; i >= 0; i–) {
MaxHeapify(arr, i);
// MinHeapify(arr,i,heapsize);
}
}
// 排序算法
public void Heap_Sort(int arr[]) {BuildMaxHeap(arr);for (int i = arr.length - 1; i > 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;heapsize --;MaxHeapify(arr, 0);// MinHeapify(arr,0,heapsize);}}// 打印
public void Print(int arr[]) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}
}
public void Print1(int arr[]) {for (int i = 0; i < arr.length+1; i++) {System.out.print(arr[i] + " ");}
}
}
PriorityQueue
package Search;
import java.util.Arrays;
//优先队列
public class PriorityQueue extends HeapSort{
public static void main(String[] args) {int arr[] = { 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };PriorityQueue p1 = new PriorityQueue();System.out.println("输出原队列:"+Arrays.toString(arr));p1.BuildMaxHeap(arr);System.out.println("输出重建队列:"+Arrays.toString(arr));p1.HeapIncreaseKey(arr, 2, 100);System.out.println("将第二个值增加后输出队列:"+Arrays.toString(arr));System.out.println("删除最大元："+p1.HeapExtractmax(arr));p1.MaxHeapInsert(arr,33);System.out.println("输出队列:"+Arrays.toString(arr));
}// 返回队列中最大关键字元素
public int HeapMaxnum(int arr[]) {return arr[0];
}// 去掉并且返回队列中中具有最大关键字的元素
public int HeapExtractmax(int arr[]) {if (heapsize < 1) {System.out.println("heap underflow!");}int max = arr[0];arr[0] = arr[heapsize-1];heapsize = heapsize-1;this.MaxHeapify(arr, 0 );return max;
}// 把元素x的值增加到k
public void HeapIncreaseKey(int arr[], int i, int key) {if (key < arr[i]) {System.out.println("error:new key is smaller than current key!");}arr[i] = key;while (i > 0 && arr[Parent(i)] < arr[i]) {int temp = arr[i];arr[i] = arr[Parent(i)];arr[Parent(i)] = temp;i = Parent(i);}
}// 把元素x的插入到队列中public void MaxHeapInsert(int arr[],int key) {heapsize = heapsize + 1;arr[heapsize-1]=Integer.MIN_VALUE;HeapIncreaseKey(arr, heapsize-1, key);}
}
这篇关于HeapSort and PriorityQueue(堆排序算法和优先队列Java代码实现)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
