中小企业为什么要建网站,有网站做淘宝客,旅行社网站 模板,在哪里申请域名堆是一种特殊的数据结构#xff0c;它是一棵完全二叉树#xff0c;且满足堆的性质#xff1a;对于每个节点#xff0c;它的值都不小于#xff08;或不大于#xff09;它的孩子节点的值。根节点的值就是堆中的最大值#xff08;或最小值#xff09;。
Java中提供了一个…
堆是一种特殊的数据结构它是一棵完全二叉树且满足堆的性质对于每个节点它的值都不小于或不大于它的孩子节点的值。根节点的值就是堆中的最大值或最小值。
Java中提供了一个Heap类可以用来实现堆的操作。Heap类是一个抽象类它定义了堆的基本操作方法如插入、删除、获取最大或最小值等。
要使用Heap类需要创建一个具体的实现类例如MaxHeap和MinHeap。这些类继承自Heap类并实现了具体的插入、删除、获取最大或最小值等方法。下面我们以MaxHeap为例来详细介绍如何实现堆。
MaxHeap的实现思路如下 定义一个数组来保存堆的元素数组下标从1开始。 定义一个变量来记录堆中元素的数量。 实现插入方法新元素插入到数组最后然后使用上滤操作将新元素沿着路径向上移动直到堆的性质被满足。 实现删除方法移除堆顶元素数组下标为1的元素然后将数组最后一个元素替换到堆顶使用下滤操作将新元素沿着路径向下移动直到堆的性质被满足。 实现获取最大值方法直接返回堆顶元素。 实现堆排序方法依次取出堆顶元素将其放到一个新的数组中然后重新调整堆。
以下是MaxHeap的代码实现
public class MaxHeapT extends ComparableT {private T[] heap; // 堆元素数组private int size; // 堆元素数量SuppressWarnings(unchecked)public MaxHeap(int capacity) {heap (T[]) new Comparable[capacity 1]; // 数组下标从1开始size 0;}public void insert(T value) {if (size heap.length - 1) {resize();}heap[size] value; // 新元素插入到数组最后swim(size); // 上滤操作}public T deleteMax() {if (size 0) {throw new NoSuchElementException();}T max heap[1]; // 堆顶元素heap[1] heap[size--]; // 将数组最后一个元素替换到堆顶sink(1); // 下滤操作heap[size 1] null; // 释放旧的堆顶元素return max;}public T getMax() {if (size 0) {throw new NoSuchElementException();}return heap[1];}public void heapSort(T[] arr) {heapify(arr); // 初始化堆for (int i size; i 0; i--) {arr[i - 1] deleteMax(); // 依次取出堆顶元素}}private void swim(int k) {while (k 1 heap[k].compareTo(heap[k / 2]) 0) { // 父节点小于当前节点上滤swap(k, k / 2);k / 2; // 移动到父节点}}private void sink(int k) {while (2 * k size) { // 如果有左孩子int j 2 * k;if (j size heap[j].compareTo(heap[j 1]) 0) { // 选择左右孩子中较大的那个j;}if (heap[k].compareTo(heap[j]) 0) { // 如果父节点不小于孩子节点下滤结束break;}swap(k, j); // 父节点和子节点交换k j; // 移动到子节点}}private void heapify(T[] arr) {heap (T[]) new Comparable[arr.length 1];size arr.length;System.arraycopy(arr, 0, heap, 1, arr.length); // 复制数组元素到堆中for (int i size / 2; i 1; i--) { // 倒序下滤从最后一个非叶子节点开始sink(i); // 下滤操作}}private void resize() {int newSize heap.length * 2;heap Arrays.copyOf(heap, newSize);}private void swap(int i, int j) {T temp heap[i];heap[i] heap[j];heap[j] temp;}
}上面的代码实现了MaxHeap类它支持插入、删除、获取最大值和堆排序等操作。堆排序的实现就是先将数组元素初始化成一个堆然后依次取出堆顶元素进行排序。
MaxHeap类中使用了泛型可以存储任意类型的元素只要实现了Comparable接口。使用时可以像下面这样创建一个MaxHeap对象然后调用其方法进行操作
MaxHeapInteger maxHeap new MaxHeap(10);
maxHeap.insert(3);
maxHeap.insert(1);
maxHeap.insert(4);
maxHeap.insert(1);
maxHeap.insert(5);
System.out.println(maxHeap.deleteMax()); // 输出5
System.out.println(maxHeap.getMax()); // 输出4Integer[] arr {3, 1, 4, 1, 5};
maxHeap.heapSort(arr);
System.out.println(Arrays.toString(arr)); // 输出[1, 1, 3, 4, 5]总的来说实现堆的关键在于实现上滤和下滤操作。上滤操作用于插入新元素时将其从叶子节点沿着路径向上移动下滤操作用于删除堆顶元素时将最后一个元素从根节点沿着路径向下移动维护堆的性质。堆排序的实现就是先将数组初始化成一个堆然后依次取出堆顶元素进行排序。最后需要注意的是在Java中实现堆可以使用Heap类但也可以自己实现一个堆类可以根据具体需求进行设计和优化。
