堆的定义：n个元素的序列{k1 , k2 , … , kn}称之为堆，当且仅当满足以下条件时：
（1）ki >= k2i 且 ki >= k(2i+1) ——大根堆
（2） ki <= k2i 且 ki <= k(2i+1) ——小根堆
简单来说：
堆是具有以下性质的完全二叉树：
（1）每个结点的值都大于或等于其左右孩子结点的值，称为大根堆（如左下图）；
或者：
（1）每个结点的值都小于或等于其左右孩子结点的值，称为小根堆（如右下图）。
我们使用数组保存二叉树结构，即是将二叉树用层序遍历方式放入数组中，如上图。
堆的元素下标存在以下关系：
小结：
设有一个无序序列 {2,5,7,8,4,6,3,0,9,1 }，下面通过图解来建初始堆。
这里有一个前提：这棵二叉树的左右子树都必须是一个堆，才能进行调整。
下面是用到的数据的一些说明：
过程文字描述如下：
通过上面的操作描述，我们写出以下代码：
public static void shiftDown(int[] array, int size, int index){
int left = 2*index +1;
while(left < size){
int min = left;
int right = 2*index +2;
if(right<size){
if(array[right] < array[left]){
min = right;
}
}
if(array[index] <= array[min]){
break;
}
int tmp = array[index];
array[index] = array[min];
array[min] = tmp;
index = min;
left = 2*index +1;
}
}
时间复杂度为 O(log(n))。
下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。
时间复杂度分析：
粗略估算，可以认为是在循环中执行向下调整，为 O(n * log(n))，（了解）实际上是 O(n)。
//建堆代码
public void createHeap(int[] array) {
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
usedSize++;
}
//根据代码 显示的时间复杂度 看起来 应该是O(n*logn) 但是 实际上是O(n)
for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
//调整
shiftDown(parent,usedSize);
}
}
根据百科解释：
普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出（first in, largest out）的行为特征。通常采用堆数据结构来实现。
所以我们在这里实现优先队列的内部原理是堆，也就是说采用堆来构建。
过程（以大堆为例）：
下面图解：
private void shiftUp(int child) {
int parent = (child-1)/2;
while (child > 0) {
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
child = parent;
parent = (child-1)/2;
}else {
break;
}
}
}
为了防止破坏堆的结构，删除时并不是直接将堆顶元素删除，而是用数组的最后一个元素替换堆顶元素，然后通过向 下调整方式重新调整成堆。
private void shiftUp(int child) {
int parent = (child-1)/2;
while (child > 0) {
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
child = parent;
parent = (child-1)/2;
}else {
break;
}
}
}
public void offer(int val) {
if(isFull()) {
//扩容
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize++] = val;
//注意这里传入的是usedSize-1
shiftUp(usedSize-1);
}
直接返回堆顶元素
public int peek() {
if(isEmpty()) {
throw new RuntimeException("优先级队列为空！");
}
return elem[0];
}
public boolean isEmpty() {
return usedSize == 0;
}
整体的代码：
public class TestHeap {
public int[] elem;
public int usedSize;
public TestHeap() {
this.elem = new int[10];
}
/**
* 向下调整函数的实现
* @param parent 每棵树的根节点
* @param len 每棵树的调整的结束位置 10
*/
public void shiftDown(int parent,int len) {
int child = 2*parent+1;
//1、最起码 是有左孩子的，至少有1个孩子
while (child < len) {
if(child+1 < len && elem[child] < elem[child+1]) {
child++;//保证当前左右孩子最大值的下标
}
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}
public void createHeap(int[] array) {
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
usedSize++;
}
//根据代码 显示的时间复杂度 看起来 应该是O(n*logn) 但是 实际上是O(n)
for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
//调整
shiftDown(parent,usedSize);
}
}
private void shiftUp(int child) {
int parent = (child-1)/2;
while (child > 0) {
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
child = parent;
parent = (child-1)/2;
}else {
break;
}
}
}
public void offer(int val) {
if(isFull()) {
//扩容
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize++] = val;
//注意这里传入的是usedSize-1
shiftUp(usedSize-1);
}
public boolean isFull() {
return usedSize == elem.length;
}
public int poll() {
if(isEmpty()) {
throw new RuntimeException("优先级队列为空！");
}
int tmp = elem[0];
elem[0] = elem[usedSize-1];
elem[usedSize-1] = tmp;
usedSize--;
shiftDown(0,usedSize);
return tmp;
}
public int peek() {
if(isEmpty()) {
throw new RuntimeException("优先级队列为空！");
}
return elem[0];
}
public boolean isEmpty() {
return usedSize == 0;
}
public void heapSort() {
int end = this.usedSize-1;
while (end > 0) {
int tmp = elem[0];
elem[0] = elem[end];
elem[end] = tmp;
shiftDown(0,end);
end--;
}
}
}
什么是TopK问题？
从arr[1, n]这n个数中，找出最大的k个数，这就是经典的TopK问题。
解决这类问题，我们往往会有以下几种思路：
我们直接讲思路三：
以这个数组{12，15，21，41，30}为例，找到前3个最大的元素。
那如果是将一组进行从小到大排序，我们该采用大根堆还是小根堆？
答案是：大根堆！
步骤如下：
总结：
public void heapSort() {
int end = this.usedSize-1;
while (end > 0) {
int tmp = elem[0];
elem[0] = elem[end];
elem[end] = tmp;
shiftDown(0,end);
end--;
}
}
public void shiftDown(int parent,int len) {
int child = 2*parent+1;
//1、最起码 是有左孩子的，至少有1个孩子
while (child < len) {
if(child+1 < len && elem[child] < elem[child+1]) {
child++;//保证当前左右孩子最大值的下标
}
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}
如文章有错误，还请各位看客老爷斧正！