欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

堆及堆排序java版

程序员文章站 2022-03-31 19:08:48
...

1.什么是完全二叉树

(1)叶子结点在n层或者n-1层
(2)从最左端开始
堆及堆排序java版

2.堆(最大堆)

(1)完全二叉树
(2)parent > childs
比如:
堆及堆排序java版
但是可能有些结构不满足堆的特性,比如:4<10,我们就需要调整成堆。
堆及堆排序java版
heapify操作:以i位置结点为parent去调整,使其满足堆的特性
堆及堆排序java版
相应的代码:

	/**
 * 堆:完全二叉树(可以用数组存储)
 *      parent > child
 *
 *  而且有: child1 = (parent * 2) + 1
 *           child2  = (parent * 2) + 2
 *
 *           parent = (child - 1) / 2;
 *  tree :完全二叉树
 *  n  : 结点数量
 *  i :表示以i为parent对堆进行调整,使其满足堆的特性
 * */
private static void heapify(int[] tree, int n, int i) {
    if (tree == null || i >= n){
        return;
    }
    // 找到parent和child中最大的结点下标
    int max = i;
    int child1 = i * 2 + 1;
    int child2 = i * 2 + 2;

    if (child1< n && tree[child1] > tree[max]){
        max = child1;
    }
    if (child2 < n && tree[child2] > tree[max]){
        max = child2;
    }
    // 说明确实需要调整,否则父结点就是最大的结点,就不用调整了
    if (max != i){
        swap(tree,i,max);
        //然后在递归的对下面的堆进行调整
        heapify(tree,n,max);
    }

}
/**
 * 交换
 * */
private static void swap(int[] tree, int i, int j) {
    int temp = tree[i];
    tree[i] = tree[j];
    tree[j] = temp;
}


要是这个tree一开始就无序呢?就咋咋都是无序的
我们就需要从最后一个parent结点开始依次向上开始调整使其变成堆(heapify操作)
堆及堆排序java版

/**
 * 如果tree刚开始就无序,没有符合堆的parent > child
 * 那么,我们就需要从最后一个叶子结点的parent开始向上调整
 * 执行heapify操作
 * */
private static void buildHeap(int[] tree, int n) {
    //最后一个节点的下标
    int lastNode = n - 1 ;
    //找到其父亲结点
    int lastParent = (lastNode - 1) >> 1 ;
    //依次调整
    for (int i = lastParent; i >=0; i--) {
        heapify(tree,n,i);
    }
}

好了,现在我们已经是一个堆了

3. 堆排序

现在我们要求需要排序?要怎么做呢?

/**
 * 堆排序
 * */
private static void heapSort(int[] tree,int n){
    // 构建一个堆
    buildHeap(tree,n);
    for (int i = n - 1; i >=0; i--) {
        //将第一个元素与最后一个元素交换(相当于把最大值换到数组末尾了)
        swap(tree,i,0);
        //调整第一个元素使其成为最大堆
        //注意现在堆大小变成i了,因为你要将最大值移出去,tree长度在变化
        heapify(tree,i,0);
    }
}


至此我们的堆排序就完成了

全部代码如下:

package com.dataConstruct;

/**
 * Created by BorisLiu on 2019/10/25
 */
public class Heap {
    /**
     * 交换
     * */
    private static void swap(int[] tree, int i, int j) {
        int temp = tree[i];
        tree[i] = tree[j];
        tree[j] = temp;
    }
    /**
     * 堆:完全二叉树(可以用数组存储)
     *      parent > child
     *
     *  而且有: child1 = (parent * 2) + 1
     *           child2  = (parent * 2) + 2
     *
     *           parent = (child - 1) / 2;
     *  tree :完全二叉树
     *  n  : 结点数量
     *  i :表示以i为parent对堆进行调整,使其满足堆的特性
     * */
    private static void heapify(int[] tree, int n, int i) {
        if (tree == null || i >= n){
            return;
        }
        // 找到parent和child中最大的结点下标
        int max = i;
        int child1 = i * 2 + 1;
        int child2 = i * 2 + 2;

        if (child1< n && tree[child1] > tree[max]){
            max = child1;
        }
        if (child2 < n && tree[child2] > tree[max]){
            max = child2;
        }
        // 说明确实需要调整,否则父结点就是最大的结点,就不用调整了
        if (max != i){
            swap(tree,i,max);
            //然后在递归的对下面的堆进行调整
            heapify(tree,n,max);
        }

    }

    /**
     * 如果tree刚开始就无序,没有符合堆的parent > child
     * 那么,我们就需要从最后一个叶子结点的parent开始向上调整
     * 执行heapify操作
     * */
    private static void buildHeap(int[] tree, int n) {
        //最后一个节点的下标
        int lastNode = n - 1 ;
        //找到其父亲结点
        int lastParent = (lastNode - 1) >> 1 ;
        //依次调整
        for (int i = lastParent; i >=0; i--) {
            heapify(tree,n,i);
        }
    }

    /**
     * 堆排序
     * */
    private static void heapSort(int[] tree,int n){
        // 构建一个堆
        buildHeap(tree,n);
        for (int i = n - 1; i >=0; i--) {
            //将第一个元素与最后一个元素交换(相当于把最大值换到数组末尾了)
            swap(tree,i,0);
            //调整第一个元素使其成为最大堆
            heapify(tree,i,0);
        }
    }



    public static void main(String[] args) {
         //int tree[] = {4,10,3,5,1,2};
        int tree[] = {2,5,3,1,10,4};

        int n = 6;
         //heapify(tree,n,0);
//         buildHeap(tree,n);
        heapSort(tree,n);

        for (int i = 0; i < n; i++) {
            System.out.println(tree[i]);
        }
    }
}

感谢阅读,若有什么问题,恭请各位大佬指正