Max heap 是一个完整的二进制树,其中节点的值大于或等于其子女的值。
在本教程中,我们将涵盖你需要知道从头开始实现Java中的MAX堆栈的一切。
Java 中的 Max Heap 数据结构
我们使用数组来表示堆积,因为堆积是一个完整的二进制树,所以没有浪费空间。
例如,让我们考虑一堆如下:
** 数组代表性是:**
Max Heap 的声明如下:
1static class MaxHeap {
2 private int[] Heap; // array
3 private int size;
4 private int maxsize;
5
6 public MaxHeap(int size) {
7 this.maxsize = size;
8 this.size = 0;
9 Heap = new int[this.maxsize + 1];
10 Heap[0] = Integer.MAX_VALUE;
11 }
堆积是存储最多堆积的数组. 构建器采用尺寸并将数组以 0 元素为无限元素进行初始化。
1、成为一个节点的父母
由于我们将堆栈存储为数组,因此获取节点的母子变得更容易。
对于位置i的元素,其父母的位置是由:
1(i)/2
在实施过程中,我们可以让家长使用:
1private int parent(int pos) {
2 return pos / 2;
3 }
二、带孩子去节点
对于位置i的节点,其子女是通过公式给出的:
左小孩:
1(2*i)
正确的孩子:
1(2*i)+ 1
注意:当您的堆栈从索引 1 开始时,此情况是正确的。如果堆栈从 0 位置开始,则值为 (2i) +1 和 (2i) +2 分别为左边和右边的孩子。
在代码中,我们执行如下:
1private int leftChild(int pos) {
2 return (2 * pos) ;
3 }
4
5 private int rightChild(int pos) {
6 return (2 * pos) + 1;
7 }
3. Heapify 新插入的元素
将一个元素插入堆栈后,它可能无法满足堆栈属性,在这种情况下,我们需要调整堆栈的位置,使它再次堆栈。
要在一个最大堆积中加重一个元素,我们需要找到最大的子女,并与当前元素交换它,我们继续这个过程,直到堆积属性在每个节点上得到满足。
为了heapify,我们从根移动到叶子,因此这也被称为 **Down Heapify。
另一个值得注意的点是,我们只在非叶节点上执行heapify。
down-heapify 函数的代码是:
1private void downHeapify(int pos) {
2
3//checking if the node is a leaf node
4 if (pos >= (size / 2) && pos <= size)
5 return;
6
7//checking if a swap is needed
8 if (Heap[pos] < Heap[leftChild(pos)] ||
9 Heap[pos] < Heap[rightChild(pos)]) {
10
11//replacing parent with maximum of left and right child
12 if (Heap[leftChild(pos)] > Heap[rightChild(pos)]) {
13 swap(pos, leftChild(pos));
14
15//after swaping, heapify is called on the children
16 downHeapify(leftChild(pos));
17 } else {
18
19 swap(pos, rightChild(pos));
20//after swaping, heapify is called on the children
21 downHeapify(rightChild(pos));
22 }
23 }
24 }
swap 函数如下:
1private void swap(int fpos, int spos) {
2 int tmp;
3 tmp = Heap[fpos];
4 Heap[fpos] = Heap[spos];
5 Heap[spos] = tmp;
6 }
您也可以使用时间循环来编写相同的代码,而不是回归。
在 down-heapify 中,我们从父母向子女移动,我们也可以以 bottom-up 方式移动,当我们以 bottom-up 方式移动时,我们将节点与其父母进行比较。
up-heapify 的代码是:
1private void heapifyUp(int pos) {
2 int temp = Heap[pos];
3 while(pos>0 && temp > Heap[parent(pos)]){
4 Heap[pos] = Heap[parent(pos)];
5 pos = parent(pos);
6 }
7 Heap[pos] = temp;
8 }
我们已经编写了 up heapify 的代码,使用一段时间循环而不是回归。
四、新增节点
新的元素被添加到数组的尽头,并执行交换,以确保堆栈属性保持。
插入的算法是:
- 增加堆积大小
- 将新元素放在堆积的末端( array)
- 从底部到顶部
插入的代码是:
1public void insert(int element) {
2 Heap[++size] = element;
3 int current = size;
4 heapifyUp(current);
5 }
5. 删除/提取节点
要从堆中删除/提取节点,我们从根中删除元素. 根总是给出最大元素。
删除的算法如下:
- 将第一个元素复制到变量
- 复制最后一个元素到第一个位置( root)。
删除的代码是:
1public int extractMax() {
2 int max = Heap[1];
3 Heap[1] = Heap[size--];
4 downHeapify(1);
5 return max;
6 }
在这里,我们使用size--来减少堆积的大小。
Max Heap在Java中的完整实施
Max Heap 的完整 Java 實施方式如下。
1package com.JournalDev;
2
3public class Main {
4 static class MaxHeap {
5 private int[] Heap;
6 private int size;
7 private int maxsize;
8
9 public MaxHeap(int size) {
10 this.maxsize = size;
11 this.size = 0;
12 Heap = new int[this.maxsize + 1];
13 Heap[0] = Integer.MAX_VALUE;
14 }
15
16 private int parent(int pos) {
17 return pos / 2;
18 }
19
20 private int leftChild(int pos) {
21 return (2 * pos) ;
22 }
23
24 private int rightChild(int pos) {
25 return (2 * pos) + 1;
26 }
27
28 private void swap(int fpos, int spos) {
29 int tmp;
30 tmp = Heap[fpos];
31 Heap[fpos] = Heap[spos];
32 Heap[spos] = tmp;
33 }
34
35 private void downHeapify(int pos) {
36 if (pos >= (size / 2) && pos <= size)
37 return;
38
39 if (Heap[pos] < Heap[leftChild(pos)] ||
40 Heap[pos] < Heap[rightChild(pos)]) {
41
42 if (Heap[leftChild(pos)] > Heap[rightChild(pos)]) {
43 swap(pos, leftChild(pos));
44 downHeapify(leftChild(pos));
45 } else {
46 swap(pos, rightChild(pos));
47 downHeapify(rightChild(pos));
48 }
49 }
50 }
51 private void heapifyUp(int pos) {
52 int temp = Heap[pos];
53 while(pos>0 && temp > Heap[parent(pos)]){
54 Heap[pos] = Heap[parent(pos)];
55 pos = parent(pos);
56 }
57 Heap[pos] = temp;
58 }
59
60 public void insert(int element) {
61 Heap[++size] = element;
62
63 int current = size;
64 heapifyUp(current);
65
66 }
67
68 public void print() {
69 for (int i = 1; i <= size / 2; i++) {
70 System.out.print(+ Heap[i] + ": L- " +
71 Heap[2 * i] + " R- " + Heap[2 * i + 1]);
72 System.out.println();
73 }
74 }
75
76 public int extractMax() {
77 int max = Heap[1];
78 Heap[1] = Heap[size--];
79 downHeapify(1);
80 return max;
81 }
82 }
83 public static void main(String[] arg)
84 {
85
86 MaxHeap maxHeap = new MaxHeap(15);
87 maxHeap.insert(1);
88 maxHeap.insert(4);
89 maxHeap.insert(2);
90 maxHeap.insert(5);
91 maxHeap.insert(13);
92 maxHeap.insert(6);
93 maxHeap.insert(17);
94
95 maxHeap.print();
96 System.out.println("The max is " + maxHeap.extractMax());
97 }
98
99}
1Output :
2
317: L- 5 R- 13
45: L- 1 R- 4
513: L- 2 R- 6
6The max is 17
结论
本教程是关于Java中的Max堆积数据结构。