前置知识：二叉树、完全二叉树
什么样的数据结构是堆
1、堆是一个完全二叉树；
2、堆中每个节点的值都必须大于等于或小于等于其字节点，每个节点大于等于子节点的堆叫大顶堆，小于等于子节点的堆叫小顶堆。
重点关注第二点，因为堆的应用就是根据堆的第二个特性来的，比如求数据流中第K大元素，我们用一个小顶堆来存储K个元素的数据，堆顶就是要求的第K大元素。
怎样实现一个堆
完全二叉树非常适合用数据来存储，堆也是一个完全二叉树，那么堆自己也适合用数据来存储数据，那么堆中的每个节点，就可以映射到数据的下标。
我们将堆存储到数据时，下标0空出不存，为了计算方便，这个在下边的堆实现代码会体现。
知道了堆的存储方式，那么往堆中存数据或从堆中删数据，都要符合堆的第二点。
堆中每个节点的值都必须大于等于或小于等于其字节点，每个节点大于等于子节点的堆叫大顶堆，小于等于子节点的堆叫小顶堆。
这个调整过程叫做堆化。
堆化有两种方法，一种是从上往下，一种是从下往上。
比如在插入数据到堆的时候，从下往上堆化，就是将要插入的数据放到堆的末尾，又因为堆是数据存储，其实就是放到了数组末尾，然后再用最末尾这个节点，跟其父节点依次比较，如果我们的堆是小顶堆，当前节点比父节点小，那么当前节点就跟父节点的值交换，然后父节点再继续跟自己的父节点比较，知道比较到堆顶，整个堆的堆化也就完成了。
从上往下堆化，常用在删除堆顶元素，堆顶元素删除后，需要从其两个字节点找出一个较小的（小顶堆），移动到堆顶，那么对应的子树都需要处理，保证符合堆的条件。
接下来我们自己来实现一个堆中，实现一个建堆的功能。
package com.my.itzhimei.algorithm;
import java.util.Random;
public class Heap {
//用数组存储堆元素
private int[] heaps;
//堆的总容量
private int n;
//当前存放的数据个数
private int curr;
public int[] getHeaps() {
return heaps;
}
public Heap(int n) {
//默认数组下标为0的位置空出不存数据,从下标为1开始存数,方便计算
this.n = n+1;
heaps = new int[n];
this.curr = 0;
}
public void insert(int data) {
if(curr >=n) {
return;
}
curr++;
heaps[curr] = data;
//数据存入heap后,需要进行堆化,这里使用从下往上的方式堆化
//也就是将元素放到堆的最后,然后从下往上一次和父节点比较大小
int i = curr;
while(i/2>0 && heaps[i] > heaps[i/2]) {
swap(heaps,i,i/2);
i = i/2;
}
}
public void swap(int[] h,int i, int j) {
//i=子节点下标,j=父节点下标
int a = h[i];
h[i] = h[j];
h[j] = a;
}
public void printHeap(Heap h) {
for(int i=1; i<h.getHeaps().length;i++) {
System.out.print(" " + h.getHeaps()[i] + "\t");
}
System.out.println();
}
public void printHeapByTree(Heap h) {
System.out.println("元素数量："+h.curr);
int height = (int)Math.ceil(Math.ceil(Math.log(h.curr))/Math.log(2));
System.out.println("树的高度："+height);
int i = 0;
for(int j=1; j<=h.curr;j++) {
if(j == Math.pow(2,i)) {
for(int m=0; m<Math.pow(2,height-i)/2; m++) {
System.out.printf("%3s",".");
}
}
if(j != Math.pow(2,i)) {
for(int m=0; m<Math.pow(2,height-i)-1; m++) {
System.out.printf("%3s",".");
}
}
System.out.printf("%3s",h.heaps[j]);
if(j>=Math.pow(2,i)+Math.pow(2,i)-1) {
i++;
System.out.println();
continue;
}
}
}
public static void main(String[] args) {
Heap h = new Heap(20);
Random r = new Random();
for(int i=0; i<7; i++) {
int i1 = r.nextInt(100);
h.insert(i1);
}
h.printHeap(h);
h.printHeapByTree(h);
}
} heaps = new int[n];
this.curr = 0;
}
public void insert(int data) {
if(curr >=n) {
return;
}
curr++;
heaps[curr] = data;
//数据存入heap后,需要进行堆化,这里使用从下往上的方式堆化
//也就是将元素放到堆的最后,然后从下往上一次和父节点比较大小
int i = curr;
while(i/2>0 && heaps[i] > heaps[i/2]) {
swap(heaps,i,i/2);
i = i/2;
}
}
public void swap(int[] h,int i, int j) {
//i=子节点下标,j=父节点下标
int a = h[i];
h[i] = h[j];
h[j] = a;
}
public void printHeap(Heap h) {
for(int i=1; i<h.getHeaps().length;i++) {
System.out.print(" " + h.getHeaps()[i] + "\t");
}
System.out.println();
}
public void printHeapByTree(Heap h) {
int height = (int)Math.ceil(Math.log(h.curr - 1)/Math.log(2));
for(int i=0; i<height; i++) {
for(int j=0; j<h.curr;j++) {
if(j%2==0) {
for(int m=0; m<Math.pow(2,height-i)/2; m++) {
System.out.printf("%3s",".");
}
}
if(j%2!=0) {
for(int m=0; m<Math.pow(2,height-i); m++) {
System.out.printf("%3s",".");
}
}
System.out.printf("%3s",h.heaps[j+1]);
if(j+1>=Math.pow(2,i)) {
break;
}
}
System.out.println();
}
}
}Heap中定义了三个必要的元素：
//用数组存储堆元素
private int[] heaps;
//堆的总容量
private int n;
//当前存放的数据个数
private int curr;当往堆中插入数据时，就是堆化的过程，整个过程的代码逻辑和我们上面的理论讲解是一致的。
public void insert(int data) {
if(curr >=n) {
return;
}
curr++;
heaps[curr] = data;
//数据存入heap后,需要进行堆化,这里使用从下往上的方式堆化
//也就是将元素放到堆的最后,然后从下往上一次和父节点比较大小
int i = curr;
while(i/2>0 && heaps[i] > heaps[i/2]) {
swap(heaps,i,i/2);
i = i/2;
}
}public void swap(int[] h,int i, int j) {
//i=子节点下标,j=父节点下标
int a = h[i];
h[i] = h[j];
h[j] = a;
}我们最后实现了两个打印，一个是按照数据顺序打印，一个是树形打印。
输出结果：
87 83 87 65 81 49 68 20 42 7 11 39 14 45 48 14 0 0 0
元素数量：16
树的高度：5
插入数据的堆化已经完成了，demo中还没有删除数据的堆化，有兴趣的可以动手试一下。