优先列队（堆）

优先列队（堆）也是一种树结构！！

package 数据结构与算法; import java.util.Arrays; // 堆的性质 // 大顶堆：父节点 > 子节点 // 小顶堆：父节点 < 子节点 // 升序排列大顶堆 // 降序排列小顶堆 // 联想堆排序，快排？ public class 树_堆结构 { public static void main(String[] args) { int[] arr = {9, 6, 8, 7, 0 ,1, 10, 4, 2}; int start = (arr.length-1)/2; heapSort(arr); System.out.println(Arrays.toString(arr)); } public static void heapSort(int[] arr) { // 开始位置是最后一个非叶子节点， 即最后一个节点的父节点 int start = (arr.length -1)/2; // 调整为大顶堆 for (int i = start; i >= 0; i--) minHeap(arr, arr.length, i); // 把数组中第0个和堆中最后一个数交换位置， 再把前面的调整为大顶堆 for (int i = arr.length- 1; i > 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; minHeap(arr, i, 0); } } public static void maxHeap(int[] arr, int size, int index) { // 左子节点 int leftNode = 2*index+1; // 右子节点 int rightNode = 2*index+2; int max = index; //和两个节点对比找出最大的节点 if (leftNode < size && arr[leftNode] > arr[max]) max = leftNode; if (rightNode < size && arr[rightNode] > arr[max]) max = rightNode; // 交换位置 swap if (max != index) { int temp = arr[index]; arr[index] = arr[max]; arr[max] = temp; // 交换后可能会排好的堆 !注意max maxHeap(arr, size, max); } } public static void minHeap(int[] arr, int size, int index) { // 左子节点 int leftNode = 2*index+1; // 右子节点 int rightNode = 2*index+2; int min = index; //和两个节点对比找出最大的节点 if (leftNode < size && arr[leftNode] < arr[min]) min = leftNode; if (rightNode < size && arr[rightNode] < arr[min]) min = rightNode; // 交换位置 swap if (min != index) { int temp = arr[index]; arr[index] = arr[min]; arr[min] = temp; // 交换后可能会排好的堆 !注意min minHeap(arr, size, min); } } }