1 实现优先队列的底层数据结构是什么？

底层结构是数组

2 实现的方法有哪些？

insert 方法 新增节点，从下往上调整堆结构。

peek方法 获得堆顶的的元素

poll 方法 删除堆顶的元素，把最后一个元素放在堆顶，调整堆结构。

3 父子节点之间的关系是什么？

父节点是i,左子节点是2*1+1，右子节点是2*i+2

如果子节点是i,父节点是(i-1)/2

4 最小堆的实现

/*** @Description: 使用数组实现的最小堆* @Date: 2021/8/5 17:20* @Author: fuguowen* @Return* @Throws*/
public class MyPriorityQueue {//存放堆数据的数组private int[] data;//当前堆的大小private int size;//堆的最大容量private int capacity;public MyPriorityQueue(int size) {data = new int[size];this.size = 0;this.capacity = size;}/*** 获取某个结点的父结点索引** @param i* @return*/private int parent(int i) {if (i == 0) {throw new RuntimeException("根结点没有父结点");}return (i - 1) / 2;}/*** 获取某个结点的左孩子索引** @param i* @return*/private int lchild(int i) {return (2 * i) + 1;}/*** 获取某个结点的右孩子索引** @param i* @returni*/private int rchild(int i) {return (2 * i) + 2;}//插入元素public void insert(int d) {if (size == capacity) {System.out.println("堆已满");return;}data[size] = d;if (size != 0) {//自底向上调整shiftUp(size);}size++;}//移除元素public int poll() {if (size == 0) {System.out.println("堆已经是空的了！");return -1;}size--;int t = data[0];//将最后一个元素放到第一个元素位置data[0] = data[size];//然后将第一个元素下移到适当位置data[size] = -1;//自顶向下调整shiftDown(0);return t;}//删除元素，交换最后一个元素，并从上到下做堆的调整private void shiftDown(int i) {while (lchild(i) <= size - 1) {int j = lchild(i);// 让j指向他的孩子结点中的大的那一个if (j + 1 <= size - 1 && data[j] > data[j + 1]) {j = j + 1;}if (data[i] < data[j]) {break;}//元素下移int t = data[i];data[i] = data[j];data[j] = t;//i记录下一次要更新的元素i = j;}}//自底向上交换元素private void shiftUp(int index) {//当前元素小于父节点元素，交换元素，称为小顶堆while (index > 0 && data[index] < data[parent(index)]) {swap(data, index, (index - 1) / 2);index = (index - 1) / 2;}}/*** @Description: 交换两个元素* @Date: 2021/8/5 17:24* @Author: fuguowen* @Return* @Throws*/public void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}//获得堆顶元素public Integer peek() {return (size == 0) ? null : data[0];}public static void main(String[] args) {int[] arr = {3, 2, 1, 3, 5, 6, 2, 8, 9, 4};int k = 3;MyPriorityQueue queue = new MyPriorityQueue(k);for (int i = 0; i < k; i++) {queue.insert(arr[i]);}for (int j = k; j < arr.length; j++) {Integer peek = queue.peek();if (arr[j] >= peek) {queue.poll();queue.insert(arr[j]);}}System.out.println(queue.peek());}
}

5 最大堆的实现

package com.mashibing.my.test202304;public class Test019 {/*** @Description: 使用数组实现的最大堆* @Date: 2021/8/5 17:20* @Author: fuguowen* @Return* @Throws*/public static class MyPriorityQueue {//存放堆数据的数组private int[] data;//当前堆的大小private int size;//堆的最大容量private int capacity;public MyPriorityQueue(int size) {data = new int[size];this.size = 0;this.capacity = size;}/*** 获取某个结点的父结点索引* @param i* @return*/private int parent(int i) {if (i == 0) {throw new RuntimeException("根结点没有父结点");}return (i - 1) / 2;}/*** 获取某个结点的左孩子索引** @param i* @return*/private int lchild(int i) {return (2 * i) + 1;}/*** 获取某个结点的右孩子索引** @param i* @returni*/private int rchild(int i) {return (2 * i) + 2;}//插入元素public void insert(int d) {if (size == capacity) {System.out.println("堆已满");return;}data[size] = d;if (size != 0) {//自底向上调整shiftUp(size);}size++;}//移除堆顶元素public int poll() {if (size == 0) {System.out.println("堆已经是空的了！");return -1;}size--;int t = data[0];//将最后一个元素放到第一个元素位置data[0] = data[size];//然后将第一个元素下移到适当位置data[size] = -1;//自顶向下调整shiftDown(0);return t;}public  int maximum(){if (size == 0) {System.out.println("堆为空");return -1;}return data[0];}//删除元素，交换最后一个元素，并从上到下做堆的调整private void shiftDown(int i) {int l = lchild(i);int r = rchild(i);int max = i;if (l < size && data[l] > data[i]) {max = l;}if (r < size && data[r] > data[max]) {max = r;}if (max != i) {swap(data, max, i);shiftUp(max);}}//自底向上交换元素private void shiftUp(int i) {//当前元素小于父节点元素，交换元素，称为小顶堆int p = parent(i);while (i > 0 && data[i] > data[p]) {swap(data, i, p);i = (i - 1) / 2;}}/*** @Description: 交换两个元素* @Date: 2021/8/5 17:24* @Author: fuguowen* @Return* @Throws*/public void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}//获得堆顶元素public Integer peek() {return (size == 0) ? null : data[0];}public static void main(String[] args) {int[] arr = {3, 2, 1, 3, 5, 6, 2, 8, 9, 4};int k = 3;MyPriorityQueue queue = new MyPriorityQueue(k);for (int i = 0; i < k; i++) {queue.insert(arr[i]);}for (int j = k; j < arr.length; j++) {Integer peek = queue.peek();if (arr[j] >= peek) {queue.poll();queue.insert(arr[j]);}}System.out.println("容量:" + k + "  指定容量的小顶堆的堆顶元素:" + queue.peek());}}
}