## 堆的基础概念

```public interface MaxHeapInterface<T extends Comparable<? super T>> {

T removeMax();

T getMax();

boolean isEmpty();

int getSize();

void clear();

}
```

## 堆的实现 – 数组

```public class MaxHeap<T extends Comparable<? super T>> implements MaxHeapInterface<T> {

//实际实现堆的数组
private T[] heap;

//指向最后一个元素的索引
private int lastIndex;

//老套路了, 安全初始化标志
boolean initialized = false;

private static final int DEFAULT_CAPACITY = 25;

private static final int MAX_CAPACITY = 10000;

MaxHeap() {
this(DEFAULT_CAPACITY);
}

@SuppressWarnings("unchecked")
MaxHeap(int size) {
if (size > MAX_CAPACITY) {
size = MAX_CAPACITY;
}

if (size < DEFAULT_CAPACITY) {
size = DEFAULT_CAPACITY;
}

heap = (T[]) new Comparable[size + 1];
lastIndex = 0;
initialized = true;
}

}
```

## 堆的实现 – add()方法

add()方法从树的角度来说, 是新增一个节点, 此外要注意的是, 由于是最大堆, 父节点一定要大于等于子节点, 因此需要比较子节点与父节点, 如果大于父节点,需要将这个节点上浮.

```@Override
public void add(T newEntry) {

//检查容量, 如果超过就需要扩大数组
checkCapacity();

//先把元素放入最后一格
lastIndex = lastIndex + 1;
heap[lastIndex] = newEntry;

int index = lastIndex;

//不断交换到当前索引为1为止
while (index != 1) {
if (heap[index].compareTo(heap[index / 2]) > 0) {
//交换
T temp = heap[index];
heap[index] = heap[index / 2];
heap[index / 2] = temp;
}
index = index / 2;
}

}
```

## 堆的实现 – removeMax()方法

```@Override
public T removeMax() {
T result = null;

if (!isEmpty()) {
int index = 1;

//交换根元素和最后一个元素, 顺便就给result赋值, 然后将最后一个位置置为null, 之后减少lastIndex
result = heap;
heap = heap[lastIndex];
heap[lastIndex] = null;
//然后减少lastIndex, lastIndex用于后边下沉判断

lastIndex = lastIndex - 1;

boolean done = false;
//还存在左节点的情况下, 找到两个子节点的较大项(也许没有右节点), 然后进行比较, 只要小于, 就交换
while (!done && 2 * index <= lastIndex) {

//如果存在右节点
if (2 * index + 1 <= lastIndex) {
//如果左节点大于右节点
if (heap[index * 2].compareTo(heap[index * 2 + 1]) > 0) {

//要下沉节点小于左节点, 进行交换
if (heap[index].compareTo(heap[index * 2]) < 0) {
T temp = heap[index];
heap[index] = heap[index * 2];
heap[index * 2] = temp;
//更新当前节点的index到左节点的位置
index = index * 2;

//下沉节点大于两个较大的, 则已经到达正确位置
} else {
done = true;
}
//如果左节点小于等于右节点, 即右节点较大
} else {
//要下沉节点小于右节点, 进行交换
if (heap[index].compareTo(heap[index * 2 + 1]) < 0) {

T temp = heap[index];
heap[index] = heap[index * 2 + 1];
heap[index * 2 + 1] = temp;

//更新当前节点的index到右节点的位置
index = index * 2 + 1;
//下沉节点大于两个较大的, 则已经到达正确位置
} else {
done = true;
}
}
//如果不存在右节点, 直接比较左节点
} else {
//要下沉节点小于左节点, 进行交换
if (heap[index].compareTo(heap[index * 2]) < 0) {
T temp = heap[index];
heap[index] = heap[index * 2];
heap[index * 2] = temp;
//下沉节点大于两个较大的, 则已经到达正确位置
index = index * 2;
} else {
done = true;
}
}

}
}

return result;
}
```

```@Override
public T getMax() {
if (isEmpty()) {
return null;
} else {
return heap;
}
}

@Override
public boolean isEmpty() {
return lastIndex == 0;
}

@Override
public int getSize() {
return lastIndex;
}

@Override
public void clear() {
for (int i = 1; i <= lastIndex; i++) {
heap[i] = null;
}
lastIndex = 0;
}

//为测试显示内部结构使用, 实际中不能直接返回内部数组的索引
public T[] toArray() {
return heap;
}
```

```@SuppressWarnings("unchecked")
private void checkCapacity() {

//如果已经满了, 即lastIndex = MAX_CAPACITY, 抛异常
if (lastIndex + 1 > MAX_CAPACITY) {
throw new RuntimeException("数组已经达到最大长度");
}

if (lastIndex + 1 == heap.length) {
//否则需要在扩大一倍和上限之间进行选择, 实际的数组长度应该是 lastIndex*2+1 和 MAX_CAPACITY+1 两个的较小值
int newLength = Math.min((lastIndex * 2 + 1), MAX_CAPACITY + 1);

T[] newArray = (T[]) new Comparable[newLength];

if (lastIndex + 1 >= 0) System.arraycopy(heap, 0, newArray, 0, lastIndex + 1);

heap = newArray;
}

}
```

## 创建堆数据结构

```private void reheap(int index) {

boolean done = false;
//还存在左节点的情况下, 找到两个子节点的较大项(也许没有右节点), 然后进行比较, 只要小于, 就交换
while (!done && 2 * index <= lastIndex) {

//如果存在右节点
if (2 * index + 1 <= lastIndex) {
//如果左节点大于右节点
if (heap[index * 2].compareTo(heap[index * 2 + 1]) > 0) {

//要下沉节点小于左节点, 进行交换
if (heap[index].compareTo(heap[index * 2]) < 0) {
T temp = heap[index];
heap[index] = heap[index * 2];
heap[index * 2] = temp;
//更新当前节点的index到左节点的位置
index = index * 2;

//下沉节点大于两个较大的, 则已经到达正确位置
} else {
done = true;
}
//如果左节点小于等于右节点, 即右节点较大
} else {
//要下沉节点小于右节点, 进行交换
if (heap[index].compareTo(heap[index * 2 + 1]) < 0) {

T temp = heap[index];
heap[index] = heap[index * 2 + 1];
heap[index * 2 + 1] = temp;

//更新当前节点的index到右节点的位置
index = index * 2 + 1;
//下沉节点大于两个较大的, 则已经到达正确位置
} else {
done = true;
}
}
//如果不存在右节点, 直接比较左节点
} else {
//要下沉节点小于左节点, 进行交换
if (heap[index].compareTo(heap[index * 2]) < 0) {
T temp = heap[index];
heap[index] = heap[index * 2];
heap[index * 2] = temp;
//下沉节点大于两个较大的, 则已经到达正确位置
index = index * 2;
} else {
done = true;
}
}

}
}
```

```@Override
public T removeMax() {
T result = null;

if (!isEmpty()) {
int index = 1;

result = heap;
heap = heap[lastIndex];
heap[lastIndex] = null;
lastIndex = lastIndex - 1;

//做完交换之后重新整理堆
reheap(index);

}

return result;
}
```

```public MaxHeap(T[] entryArray) {
this(entryArray.length);

//将数组内容复制到内部数组的从1开始的位置
System.arraycopy(entryArray, 0, heap, 1, entryArray.length);

lastIndex = entryArray.length;

//反向重新整理堆
for (int index = lastIndex / 2; index >= 1; index--) {
reheap(index);
}
}
```

```public static void main(String[] args) {

Integer[] aa = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};

System.out.println(aa.length);

MaxHeap<Integer> heap = new MaxHeap<>(aa);

System.out.println(Arrays.toString(heap.toArray()));
}
```

## 堆排序

1. 将这个数组使用reheap来排成堆的形状
2. 不断交换首元素和末尾元素, 然后对0 – n-1的位置再reheap
3. 直到 n-1 – 0 =1, 即只剩下一个元素为止.

```//对堆的startIndex到endIndex的部分执行下沉操作
//这个方法本质上和之前的完全一样, 只是索引发生了改变
private static <T extends Comparable<? super T>> void reheap(T[] array, int startIndex, int endIndex) {
boolean done = false;
//由于这里的索引正常化, 所以左节点索引会变化
int leftChildIndex = 2 * startIndex + 1;

while (!done && leftChildIndex <= endIndex) {

//确定那一边比较大, 获取较大的节点对应的数组索引
int largerChildIndex = leftChildIndex;
//如果有右节点
if (leftChildIndex + 1 <= endIndex) {
//如果右节点是比较大的点
if (array[leftChildIndex + 1].compareTo(array[leftChildIndex]) > 0) {
largerChildIndex = leftChildIndex + 1;
}
}

//比较首节点与较大的子节点, 如果小于就交换, 然后重新设置startIndex到交换后的节点, leftChildIndex到交换后的节点的左子节点
if (array[startIndex].compareTo(array[largerChildIndex]) < 0) {

T temp = array[startIndex];
array[startIndex] = array[largerChildIndex];
array[largerChildIndex] = temp;

startIndex = largerChildIndex;
leftChildIndex = largerChildIndex * 2 + 1;
} else {
done = true;
}
}
}
```

```//从数组最右边元素的父节点开始, 到数组末尾, 依次应用下沉方法, 得到一个堆
private static <T extends Comparable<? super T>> void arrangToHeap(T[] array) {
for (int i = array.length / 2; i >= 0; i--) {
reheap(array, i, array.length - 1);
}
}
```

```public static <T extends Comparable<? super T>> void sort(T[] array) {
//首先将数组弄成堆
arrangToHeap(array);

//第一次交换首尾元素

T temp = array;
array = array[array.length - 1];
array[array.length - 1] = temp;

int count = array.length;

//然后开始不断交换首尾元素并缩短范围
//由于下沉过程会自动结束, 因此无需判断实际操作的数组长度
for (int lastIndex = count - 2; lastIndex >= 0; lastIndex--) {
reheap(array, 0, lastIndex);
T temp2 = array;
array = array[lastIndex];
array[lastIndex] = temp2;
}
}
```
{"ft_lang_label":"__label__zh","ft_lang_prob":0.7233318,"math_prob":0.9897388,"size":9960,"snap":"2022-40-2023-06","text_gpt3_token_len":5636,"char_repetition_ratio":0.1676376,"word_repetition_ratio":0.325,"special_character_ratio":0.2926707,"punctuation_ratio":0.29556963,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9931925,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-10-01T15:12:45Z\",\"WARC-Record-ID\":\"<urn:uuid:dd3c1b97-b520-4687-b65c-9390a608c1ea>\",\"Content-Length\":\"52332\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:001a43b0-69ce-417d-8cdb-1eadbf700150>\",\"WARC-Concurrent-To\":\"<urn:uuid:48b7626d-525a-4d2f-97f1-c488c1d2ed44>\",\"WARC-IP-Address\":\"60.205.47.148\",\"WARC-Target-URI\":\"https://archive.conyli.cc/archives/3641\",\"WARC-Payload-Digest\":\"sha1:USHB4BAQOK3VXBZCRT2FDFJLWKDLUE73\",\"WARC-Block-Digest\":\"sha1:M6S2RXVP6TZ7HXJE2CJ4ZRFPW6LAFFWO\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-40/CC-MAIN-2022-40_segments_1664030336674.94_warc_CC-MAIN-20221001132802-20221001162802-00429.warc.gz\"}"}