堆1：堆与堆排序
堆（Heap）
堆分为大顶堆和小顶堆，堆是一颗完全二叉树。
规定如下：
- 堆是一颗完全二叉树
- 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
第一点，堆必须是一个完全二叉树。完全二叉树要求，除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。
第二点，堆中的每个节点的值必须大于等于（或者小于等于）其子树中每个节点的值。实际上，我们还可以换一种说法，堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。这两种表述是等价的。
对于每个节点的值都大于等于子树中每个节点值的堆，我们叫做“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫做“小顶堆”。
堆的存储
[[树1：二叉树基础]]里面提到完全二叉树很适合使用数组存储，堆通常也是使用数组存储。数组index为0的位置不存储元素，元素存储从1开始。
对于某index的元素E来说，其左节点L、右节点R和父节点P可以通过以下方式计算出来：
逻辑结构：
[P]
/ \
[E] [any]
/ \
[L][R]
存储结构：
[,P,E,any,L,R]
索引计算：
index(L) = index(E) * 2
index(R) = index(E) * 2 + 1
index(P) = index(E) / 2
当然，我们也可以在index=0位置存储元素，计算公式变为：
index(L) = index(E) * 2 + 1
index(R) = index(E) * 2 + 2
index(P) = (index(E) - 1) / 2实现
操作
添加元素
添加元素的思路是，将元素放入最后一个位置，然从这个位置开始向上堆化保证堆的性质不变。时间复杂度是O(logn)。
获取堆顶元素
index = 0的元素就是堆顶元素，它是堆最大或者最小的元素。时间复杂度是O(1)
移除堆顶元素
移除堆顶元素的思路是，使用最后一个元素替换堆顶元素，然后删除最后一个元素，最后从堆顶元素开始向下堆化保证堆的性质不变。时间复杂度是O(logn)
堆化
在插入元素和移除堆顶元素的的适合需要重新堆化处理以保证堆的性质。
堆化的方式有两种，一是向上堆化，通常用来添加元素的时候，二是向下堆化，通常用来删除堆顶元素的时候。
向上堆化
以大顶堆为例，向上堆化的思路是，当前元素与父元素（可以通过计算得到index）进行比较，如果当前元素比父元素大则交换元素位置，这样以此类推，使得父节点一定比子节点大。
向下堆化
以大顶堆为例，向下堆化的思路是，当前元素与左右子元素（可以通过计算得到index）进行比较，找出最大的元素的位置，如果当前元素与该元素交换位置，这样以此类推，使得子节点一定比父节点小，父节点一定是三个元素中最大的元素。
代码
实现如下：核心是向下对话和向上堆化代码。
package cn.lishiyuan.algorithm.heap;
import java.util.Arrays;
/**
* 堆
*/
public class Heap<T extends Comparable<T>> {
private T[] data;
private int size;
private int capacity;
private HeapType type;
public Heap(T[] data){
if(data == null || data.length == 0){
throw new IllegalArgumentException("data is null or empty");
}
this.data = Arrays.copyOf(data, data.length);
this.capacity = data.length;
this.size = capacity;
this.type = HeapType.MIN;
// 从最后一个非叶子节点开始堆化
for (int i = (capacity - 1) / 2; i >= 0; i--) {
heapifyDown(this.data,size,i);
}
}
public Heap(int capacity){
this(HeapType.MIN,capacity);
}
public Heap(HeapType type,int capacity) {
// 保证2的n次方
this.type = type;
this.capacity = capacity;
this.data = (T[]) new Comparable<?>[capacity];
this.size = 0;
}
// 大顶堆还是小顶堆
public enum HeapType {
BIG,
MIN
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public T find(int index) {
if(index < 0 || size <= index){
return null;
}
return data[index];
}
public void add(T element) {
if (element == null) {
throw new IllegalArgumentException("Element cannot be null");
}
if(size == capacity){
return;
}
int index= size;
size++;
data[index] = element;
// 堆化
heapifyUp();
}
public T top() {
if(isEmpty()){
return null;
}
return data[0];
}
public T removeTop() {
// 删除堆顶元素，进行堆化
if(isEmpty()){
return null;
}
T top = data[0];
data[0] = data[size - 1];
data[size - 1] = null;
size--;
heapifyDown(this.data,size,0);
return top;
}
// 删除堆顶元素后堆化
private void heapifyDown(T[] data,int size,int index) {
// 从该index进行自上而下的堆化
/**
* [a1] * / \ * [b2] [c3] * /\ /\ *[d4][e5][e6][f7] * * ``` * index(L) = index(E) * 2 + 1 * index(R) = index(E) * 2 + 2 * index(P) = (index(E) - 1) / 2 * ``` */ // 大顶堆
if(type == HeapType.BIG){
// 与每一层的子节点比较大小，找出大的那个与其交换位置
while (true){
int maxIndex = index;
int lIndex = index * 2 + 1;
int rIndex = index * 2 + 2;
if(lIndex < size && data[lIndex].compareTo(data[maxIndex]) > 0){
// 左节点比较大
maxIndex = lIndex;
}
if(rIndex < size && data[rIndex].compareTo(data[maxIndex]) > 0){
// 右节点比较大
maxIndex = rIndex;
}
if(maxIndex == index){
// 当前节点不比任何节点大了
return;
}
T temp = data[index];
data[index] = data[maxIndex];
data[maxIndex] = temp;
index = maxIndex;
}
}else {
// 与每一层的子节点比较大小，找出小的那个与其交换位置
while (true){
int minIndex = index;
int lIndex = index * 2 + 1;
int rIndex = index * 2 + 2;
if(lIndex < size && data[lIndex].compareTo(data[minIndex]) < 0){
// 左节点比较小
minIndex = lIndex;
}
if(rIndex < size && data[rIndex].compareTo(data[minIndex]) < 0){
// 右节点比较小
minIndex = rIndex;
}
if(minIndex == index){
// 当前节点不比任何节点小了
return;
}
T temp = data[index];
data[index] = data[minIndex];
data[minIndex] = temp;
index = minIndex;
}
}
}
// 添加元素后堆化
private void heapifyUp(){
int index = size - 1;
// 从该index进行自底下而上的堆化
/**
* [a1] * / \ * [b2] [c3] * /\ /\ *[d4][e5][e6][f7] * * ``` * index(L) = index(E) * 2 + 1 * index(R) = index(E) * 2 + 2 * index(P) = (index(E) - 1) / 2 * ``` * */ // 大顶堆
if(type == HeapType.BIG){
// index/2 父节点,当前节点比父节点大则交换位置
int pIndex = (index-1) / 2;
// -1 / 2 = 0
while ( index !=0 && pIndex >= 0 && data[index].compareTo(data[pIndex]) > 0){
T temp = data[index];
data[index] = data[pIndex];
data[pIndex] = temp;
index = pIndex;
pIndex = (index - 1) / 2;
}
}else {
// index/2 父节点,当前节点比父节点小则交换位置
int pIndex = (index-1) / 2;
// -1 / 2 = 0
while (index !=0 && pIndex >= 0 && data[index].compareTo(data[pIndex]) < 0){
T temp = data[index];
data[index] = data[pIndex];
data[pIndex] = temp;
index = pIndex;
pIndex = (index-1) / 2;
}
}
}
public void clear() {
size = 0;
Arrays.fill(data, null);
}
public HeapType getType() {
return type;
}
public boolean isFull() {
return capacity == size;
}
}堆排序
堆排序的思路是，对数据建堆后对数据进行n次堆排序，每次找出当前子合集最小或者最大的元素交换到末尾，依此类推，就能得到有序列表。
堆排序分两步，建堆，然后堆排序：
- 建堆，堆顶元素就是最大元素
- 堆排序，每次将堆顶元素与末尾元素，再对n-1个元素进行堆化，依次类推，直到只有只有一个元素，最终就能获得有序列表
package cn.lishiyuan.algorithm.sort;
import java.util.List;
/**
* 堆排序（大顶堆）
* <br>
* 堆排序分两步，建堆，然后堆排序
* 建堆，堆顶元素就是最大元素
* 堆排序，将堆顶元素置换到末尾，再对n-1个元素进行堆化，依次类推，最终就能获得有序列表
*/
public class HeapSort implements LeeSort{
@Override
public <T extends Comparable<T>> List<T> sort(List<T> data) {
throw new UnsupportedOperationException("sort is not implemented yet");
}
@Override
public <T extends Comparable<T>> T[] sort(T[] data) {
int size = data.length;
// 从最后一个非叶子节点开始堆化 我们对下标从 2n 开始到 1 的数据进行堆化，下标是 2n+1 到 n 的节点是叶子节点，我们不需要堆化。实际上，对于完全二叉树来说，下标从 2n+1 到 n 的节点都是叶子节点。
for (int i = (size - 1) / 2; i >= 0; i--) {
// 堆化i -> size 元素
heapify(data,size,i);
}
for (int i = size - 1; i > 0; i--) {
// 将最后的元素交换到最后一个位置
T temp = data[0];
data[0] = data[i];
data[i] = temp;
// 堆化
heapify(data,i,0);
}
return data;
}
private <T extends Comparable<T>> void heapify(T[] data,int size, int index){
// 从该index进行自上而下的堆化
/**
* [a1] * / \ * [b2] [c3] * /\ /\ *[d4][e5][e6][f7] * * ``` * index(L) = index(E) * 2 + 1 * index(R) = index(E) * 2 + 2 * index(P) = (index(E) - 1) / 2 * ``` */ // 大顶堆
// 与每一层的子节点比较大小，找出大的那个与其交换位置
while (true){
int maxIndex = index;
int lIndex = index * 2 + 1;
int rIndex = index * 2 + 2;
if(lIndex < size && data[lIndex].compareTo(data[maxIndex]) > 0){
// 左节点比较大
maxIndex = lIndex;
}
if(rIndex < size && data[rIndex].compareTo(data[maxIndex]) > 0){
// 右节点比较大
maxIndex = rIndex;
}
if(maxIndex == index){
// 当前节点不比任何节点大了
return;
}
T temp = data[index];
data[index] = data[maxIndex];
data[maxIndex] = temp;
index = maxIndex;
}
}
}空间复杂度
原地排序不消耗额外的空间。空间复杂度为O(1)
稳定性
堆排序不是稳定的排序算法，因为在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序
时间复杂度
- 建堆阶段
通过自底向上的筛选法构建初始堆，时间复杂度为 O(n)
因为叶子节点不需要堆化，所以需要堆化的节点从倒数第二层开始。每个节点堆化的过程中，需要比较和交换的节点个数，跟这个节点的高度 k 成正比。
[] 2^0 × h
/\
[][] 2^1 × (h-1)
/\ /\
[][].... 2^2 × (h-2)
.......... 2^(h-1) × (1)你可以看看。我们只需要将每个节点的高度求和，得出的就是建堆的时间复杂度。我们将每个非叶子节点的高度求和：
S1 = 1×h + 2^1×(h-1) + 2^2×(h-2) + ... + 1×2^h-1这个公式的求解稍微有点技巧，不过我们高中应该都学过：把公式左右都乘以 2，就得到另一个公式 S2。我们将 S2 错位对齐，并且用 S2 减去 S1，可以得到 S。
S1 = 1×h + 2×(h-1) + 4×(h-2)+....+ 2^(h-1) × 1
S1 = 2×h + 4×(h-1) + 8×(h-2)+....+ 2^h × 1
S= S2-S1 = -h + 2 + 2^2 + 2^3 + ... + 2^hS 的中间部分是一个等比数列，所以最后可以用等比数列的求和公式来计算
S = -h + (2^h - 2) + 2^h = 2^(h+1) - h -2因为 h=log2n，代入公式 S，就能得到 S=O(n)，所以，建堆的时间复杂度就是 O(n)。
- 调整阶段 ：每次交换堆顶与末尾元素后需调整堆，单次调整复杂度为 O(logn)，共需调整 n−1 次，总复杂度为 O(nlogn)
- 总体时间复杂度 ：建堆与调整阶段叠加，最终为 O(nlogn)，且在最坏、平均和最好情况下均保持该复杂度
评论已关闭