注册公司代理费用/百度网站优化方案

堆

heap，一棵完全二叉树，使用数组实现的，但具备完全二叉树的一些性质。一般总是满足以下性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树。（即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入）

堆一般分为以下两种形式：

• 大根堆：根节点的值最大，每个节点都大于等于其子树中所有节点的值
• 小根堆：根节点的值最小，每个节点都小于等于其子树中所有节点的值

两者的总体架构相同，不同的只是元素之间的比较规则

堆的入队和出队的时间复杂度都是O(log n)

在PriorityQueue中，最高优先级的元素总是位于队列的前面，即堆的根节点。（默认是数字越小，优先级越高），常用方法：

• peek()方法：获取队列中优先级最高的元素
• poll()方法：从队列中删除并返回优先级最高的元素
• add()方法：向队列中添加元素
• remove()方法：移除队列中的某个元素(数组中从左到右的第一个)
• size()方法：返回当前堆中的元素个数
• clear()方法：清空堆中的元素，重置堆

PriorityQueue底层使用最小堆来实现，能够自动维护堆的性质。

在实现堆的过程中，通常使用数组来存储堆元素，并通过一些算法实现堆的插入、删除等操作。

小根堆

数组递归实现小根堆

import java.util.*;public class MinHeap {private int[] heap;     //用于实现堆的数组private int size;       //当前数组中最后一个元素的索引private int maxSize;    //总数组长度public MinHeap(int maxSize) {this.maxSize = maxSize;this.size = 0;//从索引为1的位置存储堆中的元素heap = new int[this.maxSize + 1];heap[0] = Integer.MIN_VALUE;}// 获取传入元素的父元素private int parent(int pos) {return pos / 2;}// 获取传入元素的左子元素private int leftChild(int pos) {return 2 * pos;}// 获取传入元素的右子元素private int rightChild(int pos) {return (2 * pos) + 1;}//判断是否是叶子结点private boolean isLeaf(int pos) {return pos > (size / 2) && pos <= size;}//交换位置private void swap(int pos1, int pos2) {int tmp = heap[pos1];heap[pos1] = heap[pos2];heap[pos2] = tmp;}//小根堆化，对传入的元素作为父节点的子树进行重构，用于在插入或删除元素后重新调整堆以保持小根堆的性质private void minHeapify(int pos) {if (!isLeaf(pos)) {//不是叶子结点//如果父元素比左子元素或右子元素大if (heap[pos] > heap[leftChild(pos)] || heap[pos] > heap[rightChild(pos)]) {//交换父元素和两子节点中较小的那个元素，然后重构对应的子树if (heap[leftChild(pos)] < heap[rightChild(pos)]) {swap(pos, leftChild(pos));minHeapify(leftChild(pos));} else {swap(pos, rightChild(pos));minHeapify(rightChild(pos));}}}}//向堆中插入元素public void insert(int element) {if (size >= maxSize) {return;}heap[++size] = element;int current = size;//插入的元素比对应的父元素小，交换位置，不断向上重构while (heap[current] < heap[parent(current)]) {swap(current, parent(current));current = parent(current);}}//获取最小的元素，将最后一个元素放入到原最小元素的位置，然后重构public int extractMin() {int popped = heap[1];heap[1] = heap[size--];minHeapify(1);return popped;}//不断根据父元素打印子节点的元素public void print() {for (int i = 1; i <= size / 2; i++) {System.out.print(" Parent: " + heap[i] + " Left child: " + heap[2 * i] + " Right child: " + heap[2 * i + 1]);System.out.println();}}public static void main(String[] args) {MinHeap minHeap = new MinHeap(10);minHeap.insert(5);minHeap.insert(3);minHeap.insert(17);minHeap.print();System.out.println("The Min val is " + minHeap.extractMin());}
}

数组非递归实现小根堆

import java.util.Arrays;public class MinHeap {private int[] heap;private int size;public MinHeap(int capacity) {heap = new int[capacity];size = 0;}public void insert(int val) {if (size == heap.length) {//如果空间不够则将数组的长度扩充一倍heap = Arrays.copyOf(heap, size * 2);}heap[size++] = val;int i = size - 1;while (i > 0 && heap[i] < heap[(i - 1) / 2]) {int temp = heap[i];heap[i] = heap[(i - 1) / 2];heap[(i - 1) / 2] = temp;i = (i - 1) / 2;}}public int pop() {if (size == 0) {throw new IllegalStateException("Heap is empty");}int root = heap[0];heap[0] = heap[--size];int i = 0;while (i * 2 + 1 < size) {int child = i * 2 + 1;//如果右节点存在而且比左节点小，则指向右节点，否则指向左节点if (child + 1 < size && heap[child + 1] < heap[child]) {child++;}if (heap[child] < heap[i]) {int temp = heap[i];heap[i] = heap[child];heap[child] = temp;i = child;} else {break;}}return root;}public boolean isEmpty() {return size == 0;}
}

在 insert() 方法中，先将元素插入数组末尾，然后将其上移至合适位置，直到父节点小于等于该元素或者该元素上移到根节点为止。在 pop() 方法中，将根节点弹出后，将数组末尾元素放置根节点处，然后将其下移至合适位置，直到子节点大于等于该元素或者该元素下移到叶子节点为止。

非递归实现，因此空间复杂度较递归实现会小一些，但是代码实现会更加复杂。

非递归实现中需要学习的还有：

抛出异常

if (size == 0) {throw new IllegalStateException("Heap is empty");
}

扩充堆大小

heap = Arrays.copyOf(heap, size * 2);

PriorityQueue实现小根堆

	public static void main(String[] args) {//可以直接使用PriorityQueue实现小根堆，因为PriorityQueue内部默认就是使用小根堆实现的//PriorityQueue<Integer> minHeap = new PriorityQueue<>();//传入了一个Comparator对象，重写了compare方法，使得PriorityQueue中的元素按照从小到大的顺序排列。PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {public int compare(Integer a, Integer b) {return a - b;}});minHeap.add(10);minHeap.add(20);minHeap.add(15);System.out.println("Smallest element: " + minHeap.peek());System.out.println("Removed element: " + minHeap.poll());System.out.println("New smallest element: " + minHeap.peek());}

小根堆的实现可以使用Java中的PriorityQueue类，只需要在创建PriorityQueue对象时传入一个Comparator对象，实现Comparator的compare方法来定义小根堆的比较方式。

大根堆

数组递归实现大根堆

import java.util.*;public class MaxHeap {private int[] heap;     //用于实现堆的数组private int size;       //当前数组中最后一个元素的索引private int maxSize;    //总数组长度public MaxHeap(int maxSize) {this.maxSize = maxSize;this.size = 0;//从索引为1的位置存储堆中的元素heap = new int[this.maxSize + 1];heap[0] = Integer.MAX_VALUE;}// 获取传入元素的父元素private int parent(int pos) {return pos / 2;}// 获取传入元素的左子元素private int leftChild(int pos) {return 2 * pos;}// 获取传入元素的右子元素private int rightChild(int pos) {return (2 * pos) + 1;}//判断是否是叶子结点private boolean isLeaf(int pos) {return pos > (size / 2) && pos <= size;}//交换位置private void swap(int pos1, int pos2) {int tmp = heap[pos1];heap[pos1] = heap[pos2];heap[pos2] = tmp;}//小根堆化，对传入的元素作为父节点的子树进行重构private void maxHeapify(int pos) {if (!isLeaf(pos)) {//不是叶子结点//如果父元素比左子元素或右子元素小if (heap[pos] < heap[leftChild(pos)] || heap[pos] < heap[rightChild(pos)]) {//交换父元素和两子节点中较小的那个元素，然后重构对应的子树if (heap[leftChild(pos)] > heap[rightChild(pos)]) {swap(pos, leftChild(pos));maxHeapify(leftChild(pos));} else {swap(pos, rightChild(pos));maxHeapify(rightChild(pos));}}}}//向堆中插入元素public void insert(int element) {if (size >= maxSize) {return;}heap[++size] = element;int current = size;//插入的元素比对应的父元素小，交换位置，不断向上重构while (heap[current] > heap[parent(current)]) {swap(current, parent(current));current = parent(current);}}//获取最小的元素，将最后一个元素放入到原最小元素的位置，然后重构public int extractMax() {int popped = heap[1];heap[1] = heap[size--];maxHeapify(1);return popped;}//不断根据父元素打印子节点的元素public void print() {for (int i = 1; i <= size / 2; i++) {System.out.print(" Parent: " + heap[i] + " Left child: " + heap[2 * i] + " Right child: " + heap[2 * i + 1]);System.out.println();}}public static void main(String[] args) {MaxHeap maxHeap = new MaxHeap(10);maxHeap.insert(5);maxHeap.insert(3);maxHeap.insert(17);maxHeap.print();System.out.println("The Max val is " + maxHeap.extractMax());}
}

PriorityQueue实现大根堆

	public static void main(String[] args) {// 传入了一个Comparator对象，重写了compare方法，使得PriorityQueue中的元素按照从大到小的顺序排列。PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {public int compare(Integer a, Integer b) {return b - a;}});maxHeap.add(10);maxHeap.add(20);maxHeap.add(15);System.out.println("Max element: " + maxHeap.peek());System.out.println("Removed element: " + maxHeap.poll());System.out.println("New Max element: " + maxHeap.peek());}