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());
}
}
}
