堆的建立

一般采用数组a[n]来存储堆。首先要知道很重要的一点:当a[i]作为父结点的时候,其两个左右子结点为:a[2i+1]、a[2i+2];而当a[i]作为子结点时,其父结点为a[(i-1)/2](这个可以根据前面一条推算出来)。

 建一个新堆的过程:1)从最后一个父节点开始(下标为n/2-1),将其为根结点的子树调整成一个堆。然后是倒数第二个父结点,将其为根节点的子树调整成一个堆。最后调整真正意义上的根节点。  2)当1)中子树的层数不仅仅只有2层时,当第一层和第二层交换后,有可能交换到第二层的数据并不满足堆的性质,需要将其交换到第三层,所以当子树的层数超过两层时,需要一层层地往下交换,直到最高层。

下面用java代码实现。

package test;

/**
 *  @author hushunfeng
 *  
 *  堆排序
 *  大顶堆
 *  
 */
public class HeapSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] array = {10,20,30,40,50,60,70,80};
        createHeap(array);
        for(int i=0;i<8;i++) {
            System.out.println(array[i]);
        }
        
    }
    
    /**
     * 将无序序列进行建堆
     * @param array 要建的堆
     */private static void createHeap(int[] array) {
        int heapNum = array.length;
        //根据建堆过程,先从第n/2个元素开始
        //它是最后一个非终端结点
        for(int i = heapNum/2-1; i >= 0; i--) {
            adjustNode(array,i);
        }
    }
    
    /**
     * 
     * 将parentNode为根结点的子树调整成一个最大堆
     * @param array 要调整的无序序列,以数组的形式进行存储
     * @param parentNode  以此结点为根结点建立子树
     * 
     */
    //由于我们采用的是大顶堆,父结点要调整成大于子结点
    private static void adjustNode(int[] array,int parentNode) {
        
        //数组长度
        int arrayNum = array.length;
        //跳动的父结点游标(在子树层数大于2层时适用)
        int parentIndex = parentNode;
        //左子结点
        int childLeftNode = 2*parentIndex+1;
        //右子结点
        int childRightNode = 2*parentIndex+2;
        //
        int maxNode;
        
        //将可能要跳动的父结点的数据缓存起来
        int temp = array[parentNode];
        
        //不断地跳动父结点的游标
        //防止右子结点不存在这种情况,不然会内存溢出
        while(childLeftNode<arrayNum) {
            //此种情况下已经不存在右结点了
            if(childLeftNode==arrayNum-1) {
                maxNode = childLeftNode;
            }
            else {
                //先比较左右子结点
                if(array[childLeftNode]>array[childRightNode])
                    maxNode = childLeftNode;
                else 
                    maxNode = childRightNode;
            }
            
            //比较,交换位置
            if(array[parentIndex]<array[maxNode]) {
                //将较大的子结点交换到父结点的位置
                array[parentIndex] = array[maxNode];
                array[maxNode] = temp;
                //往下移一层,再进行一次比较交换操作
                //原先的子结点现在变成了父结点
                parentIndex = maxNode;
                //下一层的子结点
                childLeftNode = 2*parentIndex+1;
                childRightNode = 2*parentIndex+2;
            }
            //如果判断出父结点为最大,直接跳出循环
            //无需再做交换动作,因为下面的元素都已经排成了大堆
            else break;
            
        }
        
    }
    
}
原文地址:https://www.cnblogs.com/hushunfeng/p/3911161.html