简介
堆对于排序算法是一个比较常用的数据结构，下面我就使用Java语言来实现这一算法
首先，我们需要知道堆的数据结构的形式，其实就是一个特殊的二叉树。但是这个二叉树有一定的特点，除了是完全二叉树以外，对于最大堆而言，堆顶元素的值是最大的，而且对于堆的每一个子树也是一个小一号的最大堆；同样对于最小堆，性质相反就可以了。
我以最大堆为例：
要实现堆的初始化操作，就是先按照给定的元素创建一棵完全二叉树，然后从末尾节点进行不断地调整的过程。调整的原则是：比较要进行放置的当前节点与其父节点的数值的大小，若要进行放置的当前节点的值小于其父节点，那么当前节点所在位置符合最大堆的定义，要进行放置的当前节点放在此处是比较合适的；如果要进行放置的当前节点的值大于其父节点的值，那说明放在当前节点是不合适的，那么就需要将当前节点的值与其父节点的值进行交换，然后原父节点变为新的要进行放置的当前节点。循环比较；终止条件就是当前节点没有父节点，但此时的调整也许并没有结束，我们只需要让堆顶元素为要插入的值即可。至此，最大堆的插入和调整过程结束。
代码如下：
public boolean insert(int x){
if(currentSize==MAXSIZE){
System.out.println("Sorry,this heap is full!");
return false;
}
//如果堆不满的话
currentSize++;
int flag=currentSize-1;
while(flag>0){
int parent=(flag-1)/2;
if(heap[parent]>x){
heap[flag]=x;
return true;
}else{
heap[flag]=heap[parent];
flag=parent;
}
}
heap[0]=x;
return true;
}
siftDown过程：给定一个节点的位置，对其进行调整，使之符合最大堆的定义，这个过程就是我们要实现的过程。调整原则如下：
对于当前节点i而言，其孩子节点的下标满足左节点为2i+1,右节点为2i+2;在进行调整的过程中，只需要比较当前节点与其子节点中最大的节点进行调整即可。具体的代码逻辑可在代码中看到：
public void siftDown(int flag){
int want=flag;
int x=heap[flag];
while(want<currentSize){
int lChild=2*want+1;
int rChild=2*want+2;
int MAXChildNumber;
if(lChild>currentSize){ //没有孩子节点
heap[want]=x;
}else{ //有两个孩子节点
if(lChild<currentSize){
MAXChildNumber=heap[lChild]>heap[rChild]?lChild:rChild;
}else{
MAXChildNumber=lChild;
}
if(heap[MAXChildNumber]<x){
heap[want]=x;return;
}else{
heap[want]=heap[MAXChildNumber];
want=MAXChildNumber;
}
}
}
}
堆顶元素的删除，我们对堆的操作基本桑就是为了获得这个堆的最值，那么毫无疑问，堆顶元素就是我们要研究的对象。下面是代码逻辑：
public int deleteTop(){
if(currentSize<0){
System.out.println("Sorry, this heap is empty!");
return -1;
}
int target=heap[0];
int substitute=heap[currentSize-1];
this.currentSize--;
heap[0]=substitute;
siftDown(0);
return target;
}
下面是详细的代码
package test.maxHeap;
public class MaxHeap {
private int []heap ;
private int currentSize;
private static int MAXSIZE ;
public MaxHeap(int n){
heap=new int[n];
currentSize=0;
MAXSIZE=n;
}
public boolean insert(int x){
if(currentSize==MAXSIZE){
System.out.println("Sorry,this heap is full!");
return false;
}
//如果堆不满的话
currentSize++;
int flag=currentSize-1;
while(flag>0){
int parent=(flag-1)/2;
if(heap[parent]>x){
heap[flag]=x;
return true;
}else{
heap[flag]=heap[parent];
flag=parent;
}
}
heap[0]=x;
return true;
}
public void siftDown(int flag){
int want=flag;
int x=heap[flag];
while(want<currentSize){
int lChild=2*want+1;
int rChild=2*want+2;
int MAXChildNumber;
if(lChild>currentSize){ //没有孩子节点
heap[want]=x;
}else{ //有两个孩子节点
if(lChild<currentSize){
MAXChildNumber=heap[lChild]>heap[rChild]?lChild:rChild;
}else{
MAXChildNumber=lChild;
}
if(heap[MAXChildNumber]<x){
heap[want]=x;return;
}else{
heap[want]=heap[MAXChildNumber];
want=MAXChildNumber;
}
}
}
}
public int deleteTop(){
if(currentSize<0){
System.out.println("Sorry, this heap is empty!");
return -1;
}
int target=heap[0];
int substitute=heap[currentSize-1];
this.currentSize--;
heap[0]=substitute;
siftDown(0);
return target;
}
}
好了，编码已经完成。下面我们就要检验一下是否正确吧。
public class MaxHeapTest {
public static void main(String []args){
MaxHeap maxHeap=new MaxHeap(7);
for(int i=1;i<=7;i++){
maxHeap.insert(i);
}
for(int i=0;i<7;i++){
System.out.print(maxHeap.deleteTop()+" ");
}
System.out.println("\n");
}
}
接下来是程序的运行结果：
7 6 5 4 3 2 1
//可见，对于最大堆，删除堆顶的操作实际上就是完成了对堆的排序任务，也证明了我们的代码是正确的
总结：
堆的操作很重要，我们更要学会对于堆的应用，这样的数据结构才能使得程序的运行更加的高效和流畅。对于最小堆，我们只需要在插入方法，sift方法内稍加修改即可（也就是将值的代销变换关系进行调整）。这样就同样能实现最小堆的创建和相关的操作了。
代码中可能存在不太恰当地地方，希望大家予以批评指正，期待与你们共同进步！
网友评论