最大堆是一种数据结构,使用完全二叉树来实现,每一个节点都比它的左右孩子节点要大(有点类似于金字塔,数值最大的在塔顶,数值小的在塔底,高度越高,数值越大)
这种结构最适合做什么呢?它,最适合于在一坨数据中找最大值。为甚?大家想想,既然在任何时候塔顶的数都是最大的,这不就意味着我们在任何时候都可以直接抓取最大值了吗,完事了塔顶又是最大值,我们又一次拥有了抓取最大值的机会…如此循环反复,取之不尽用之不竭,子子孙孙无穷无尽也。
堆是怎么实现的呢?
堆的创建
一般来说,堆的物理数据结构是数组(毕竟堆使用了完全二叉树,数组的最经济最划算的选择,根据孩子找父母或是根据父母找孩子都异常简单与方便),数组的第一个元素被放弃使用,因为我们使用child / 2
的公式找父母,使用parent * 2
与parent * 2 + 1
找左右孩子。
我们首先将所有元素存入数组中,之后从最后一个非叶子节点开始进行调整(如果最大那个孩子比它大,就将它与那个孩子交换,交换后也许它又比新孩子小,就又要调整…如此循环不断),直到调整至根节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| private void create(List<Integer> data) { if (!this.data.isEmpty()) { this.data.clear(); }
this.data.add(0);
this.data.addAll(data);
int parent, child; for (int i = (this.data.size() - 1) / 2; i >= 1; i--) { parent = i;
while (parent <= (this.data.size() - 1) / 2) { child = parent * 2;
if (child + 1 <= (this.data.size() - 1) && this.data.get(child) < this.data.get(child + 1)) { child = child + 1; }
if (this.data.get(parent) < this.data.get(child)) { swap(parent, child); parent = child; } else { break; } }
} }
|
从上面分析可知,平均复杂度是O(n),最差情况是O(nLogn)
往堆中插入一个数据
由于堆使用了完全二叉树,往堆中插入一个数据时,最好插入到数组尾部(插到其它地方需要移动数组,效率会被拉低),之后将该数据与父母节点比较,并相应做交换,使其逐渐地上浮到相应的位置。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| private void insert(Integer element) { this.data.add(element);
int parent, child = this.data.size() - 1;
for (int i = (this.data.size() - 1) / 2; i >= 1; ) { parent = i; if (this.data.get(parent) < this.data.get(child)) { swap(parent, child); child = parent; i = i / 2; } else { break; } } }
|
时间复杂度是O(LogN)
删除堆中数组某个下标的数据
想要删除,直接将最后一个数据覆盖欲删除的数据,之后进行调整即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| private void delete(int index) { this.data.set(index, this.data.get(this.data.size() - 1)); this.data.remove(this.data.size() - 1);
int parent = index, child;
for (; parent >= (this.data.size() - 1) / 2; ) { child = parent * 2;
if (child > this.data.size() - 1) { return;
} else if (child < this.data.size() - 1) { if (this.data.get(child) < this.data.get(child + 1)) child = child + 1;
} else if (child == this.data.size() - 1) {
}
swap(parent, child);
parent = child; } }
|
时间复杂度是O(LogN)