数据结构复习—堆排序

二叉树的顺序存储

1. 顺序存储只能存储完全二叉树
2. 完全二叉树：除二叉树最后一层，其余各层均满，并且最后一层元素全集中在左侧

将二叉树存储在数组中，即二叉树的顺序存储，图示中二叉树的存储顺序，与数组中元素下标一致，因此，二叉树的顺序存储中，根节点下标为0，第n个元素的左子节点：2n+1，第n个元素的右子节点：2n+2，第n个元素的父节点：（n-1）/2
顺序存储二叉树的遍历

public class Main {
    public static void main(String[] args) {
        int[] data=new int[]{2,34,5,4,1,4,55,41};
        ArrayBinaryTree BT=new ArrayBinaryTree(data);
        BT.frontShow();
    }
}
//构建顺序存储二叉树类
public class ArrayBinaryTree {
    int[] data;

    public ArrayBinaryTree(int[] data) {
        this.data = data;
    }

    public void frontShow(){
        frontShow(0);
    }

    public void frontShow(int index) {
        if (data == null || data.length == 0) {
            return;
        }
        System.out.print(data[index] + " ");
        if (2 * index + 1 < data.length) {
            frontShow(2 * index + 1);
        }
        if (2 * index + 2 < data.length) {
            frontShow(2 * index + 2);
        }
    }
}

二叉树转换为大/小顶堆

1. 大/小顶堆：每个节点均大于/小于其左右子节点的二叉树成为大顶堆/小顶堆结构
   大顶堆：
   
2. 二叉树转为大顶堆二叉树

import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        int[] data=new int[]{2,34,5,4,1,4,55,41};
        //maxHeap()方法，每一次排序一个子树，因此需要从叶节点的父节点开始，向根节点遍历，最后将二叉树排序为大顶堆
        for(int i=(data.length-2)/2;i>=0;i--){
            maxHeap(data,i);
        }
        System.out.println(Arrays.toString(data));
    }

    /**
     * 将一个子树排序为大顶堆
     * @param data  顺序存储二叉树
     * @param index 将子树排序为大顶堆的父节点
     */
    public static void maxHeap(int[] data,int index){
        //左子节点
        int leftNode=2*index+1;
        //右子节点
        int rightNode=2*index+2;
        //和两个子节点相比找出最大值
        int max=index;
        if(leftNode<data.length && data[max]<data[leftNode]){
            max=leftNode;
        }
        if(rightNode<data.length && data[max]<data[rightNode]){
            max=rightNode;
        }
        //交换位置
        if(max!=index){
            int temp=data[index];
            data[index]=data[max];
            data[max]=temp;
            //交换之后可能会影响子节点以后的排序，因此要从交换的子节点到叶节点重新大顶堆排序
            maxHeap(data,max);
        }
    }
}

基于大/小顶堆的堆排序

大（小）顶堆排序将顺序存储二叉树中最大（小）元素值放置于根节点，因此可以进行堆排序，依次将根节点弹出，再重新对剩下的二叉树进行排序

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] data=new int[]{2,34,5,4,1,4,55,41};
        //从j=data.length-1开始遍历，没遍历一次将data[j]的元素与根节点（data[0]）的元素进行交换，并通过引入的参数length，
        //对除j外的子树进行下一次遍历，每一次都会将子树的最大值放在最后，遍历完成即完成排序
        for(int j=data.length-1;j>0;j--) {
            for (int i = (j-1) / 2; i >= 0; i--) {
                maxHeap(data,j+1,i);
            }
            int temp=data[0];
            data[0]=data[j];
            data[j]=temp;
        }
        System.out.println(Arrays.toString(data));
    }

    /**
     * 将一个子树排序为大顶堆
     * @param data  顺序存储二叉树
     * @param length 子树范围 
     * @param index 将子树排序为大顶堆的父节点
     */
    public static void maxHeap(int[] data,int length,int index){
        //左子节点
        int leftNode=2*index+1;
        //右子节点
        int rightNode=2*index+2;
        //和两个子节点相比找出最大值
        int max=index;
        if(leftNode<length && data[max]<data[leftNode]){
            max=leftNode;
        }
        if(rightNode<length && data[max]<data[rightNode]){
            max=rightNode;
        }
        //交换位置
        if(max!=index){
            int temp=data[index];
            data[index]=data[max];
            data[max]=temp;
            //交换之后可能会影响子节点以后的排序，因此要从交换的子节点到叶节点重新大顶堆排序
            maxHeap(data,length,max);
        }
    }
}

.