加盟商网站建设,代理记账一般多少钱一个月,永兴县网站建设服务商,qq企业邮箱怎么开通注册文章目录 把普通数组转换大顶堆数组堆增删改查替换堆排序 把普通数组转换大顶堆数组 该方式适用索引为0起点的堆 在堆#xff08;Heap#xff09;这种数据结构中#xff0c;节点被分为两类#xff1a;叶子节点#xff08;Leaf Nodes#xff09;和非叶子节点#xff08;N… 文章目录 把普通数组转换大顶堆数组堆增删改查替换堆排序 把普通数组转换大顶堆数组 该方式适用索引为0起点的堆 在堆Heap这种数据结构中节点被分为两类叶子节点Leaf Nodes和非叶子节点Non-Leaf Nodes。 叶子节点是指没有子节点的节点它们位于堆的最底层。在堆中叶子节点的数量总是大于或等于非叶子节点的数量。 非叶子节点是指至少有一个子节点的节点它们位于堆的上层。在二叉堆Binary Heap中非叶子节点的数量总是等于总节点数的一半向上取整。 在堆的操作中非叶子节点的重要性体现在维护堆的性质如最大堆或最小堆方面。当插入或删除节点时可能需要对非叶子节点进行调整以确保堆的性质得到维护。 package Heap;import java.util.Arrays;//大顶堆
public class MaxHeap {int [] array;int size;public MaxHeap(int capacity){this.arraynew int[capacity];}public MaxHeap(int [] array){this.arrayarray;this.sizearray.length;heapify();}//建堆private void heapify(){
// size/2-1找到非叶子节点for (int isize/2-1;i0;i--){down(i);}}//将 parent 索引处的元素下潜与两个孩子较大者交换直至没孩子//或者孩子没他大private void down(int parent){int left parent*21;int rightleft1;int max parent;if (leftsize array[left] array[max]){maxleft;}if (leftsize array[right] array[max]){maxright;}if (max!parent){//找到了更大的孩子swap(max,parent);down(max);}}//交换两个索引private void swap(int i,int j){int t array[i];array[i]array[j];array[j]t;}public static void main(String[] args) {int [] arr {1,2,3,4,5,6,7};MaxHeap maxHeap new MaxHeap(arr);System.out.println(Arrays.toString(maxHeap.array));}
}
堆增删改查替换
package Heap;import java.util.Arrays;// 大顶堆
public class MaxHeap {int[] array;int size;public MaxHeap(int capacity) {this.array new int[capacity];}public MaxHeap(int[] array) {this.array array;this.size array.length;heapify();}// 获取堆顶元素public int peek() {return array[0];}// 删除堆顶元素public int poll() {int top array[0];swap(0, size - 1);size--;down(0);return top;}// 删除指定索引public int poll(int index) {int delete array[index];swap(index, size - 1);size--;// 维护堆的性质if (index 0 array[index] array[(index - 1) / 2]) {up(index);} else {down(index);}return delete;}// 替换指定索引的元素public void replace(int index, int value) {int oldValue array[index];array[index] value;// 维护堆的性质if (value oldValue) {up(index);} else {down(index);}}// 在堆尾部添加元素public void add(int value) {array[size] value;size;up(size - 1);}// 建堆private void heapify() {// size/2-1找到非叶子节点for (int i size / 2 - 1; i 0; i--) {down(i);}}// 将 parent 索引处的元素下沉与两个孩子较大者交换直至没孩子// 或者孩子没他大private void down(int parent) {int left parent * 2 1;int right left 1;int max parent;if (left size array[left] array[max]) {max left;}if (right size array[right] array[max]) {max right;}if (max ! parent) { // 找到了更大的孩子swap(max, parent);down(max);}}// 将 child 索引处的元素上浮与父节点比较直至父节点大于等于它private void up(int child) {int parent (child - 1) / 2;while (child 0 array[child] array[parent]) {swap(child, parent);child parent;parent (child - 1) / 2;}}// 交换两个索引private void swap(int i, int j) {int t array[i];array[i] array[j];array[j] t;}public static void main(String[] args) {int[] arr {1, 2, 3, 4, 5, 6, 7};MaxHeap maxHeap new MaxHeap(arr);System.out.println(Arrays.toString(maxHeap.array));maxHeap.add(8);System.out.println(Arrays.toString(maxHeap.array));maxHeap.replace(3, 9);System.out.println(Arrays.toString(maxHeap.array));maxHeap.poll(2);System.out.println(Arrays.toString(maxHeap.array));}
}堆排序
