堆与最大堆

这篇博客主要叙述最大堆

数据结构中的堆和操作系统的堆有点不太一样:操作系统的堆大多用链表的形式,而数据结构中的堆使用的是完全二叉树.

既然它是一个完全二叉树,因此就有一下性质:叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树(来自度娘),也就是说,增加结点时只能从最下层从左到右的增加结点,删除时也只能从最下层从右到左的删除.

它有一个重要的兄弟"最大堆,我们从以下几个方面来重点讨论一下最大堆:

1. 性质
2. 重要的方法
3. 构造函数
4. 全部代码

一.性质

二.重要的方法

这里我先使用了接口,说明它们的作用

在最大堆的类中,首先要声明整个堆的全局变量:

getCount():

isEmpty():

insert(int item):

这里用到了一个私有的方法 shiftUp ,目的是在插入数据后,使得整个堆仍旧满足最大堆的性质

private shiftUp():

extrackMax():

这里用到了私有方法 shiftDown,同样是为了让它删除数据后整个堆保持最大堆

private shiftDown():

三.构造函数

它有两个构造函数,一个是创建一个限定空间的空堆,另一个是通过数组创建一个堆

四.全部代码

package com.heap;

/**
 * 最大堆:
 *      >这里使用 data[] 数组来保存最大堆,data[0]不使用,data[1]表示根节点,data[2]表示根节点左子树中的根节点,依次类推
 * 性质:
 *      >最大堆满足完全二叉树的性质
 *      >父节点的值大于两个子节点
 * 如果使用数组下标 1 存储第一个元素
 *      >下标为 k 的节点的父节点为 k / 2;
 *      >下标为 k 的节点的左孩子为 2 * k;
 *      >下标为 k 的节点的右孩子为 2 * k + 1;
 * 如果使用数组下标 0 存储第一个元素
 *      >下标为 k 的节点的父节点为 (k - 1) / 2;
 *      >下标为 k 的节点的左孩子为 2 * k + 1;
 *      >下标为 k 的节点的右孩子为 2 * k + 2;
 */
public class MaxHeap implements IMaxHeap {

    private int[] data; //最大堆的载体,使用数组来承载
    private int num;    //记录传入的最大空间,防止数组越界
    private int count;  //记录已经存储的数量

    //插入元素时使用,注意 k 表示下标
    private void shiftUp(int k) {
        //循环的检查它是否大于父节点,如果大于父节点,就要交换它(data[k])与父节点(data[k/2])的位置,来满足最大堆的定义
        while ((data[k / 2] < data[k]) && (k > 1)) {
            //交换 data[k/2] 与 data[k]
            int temp = data[k / 2];
            data[k / 2] = data[k];
            data[k] = temp;
            //更新k,现在data[k/2]即为新插入的那个值
            k /= 2;
        }
    }

    //删除节点时使用,注意 k 表示下标
    private void shiftDown(int k) {
        //循环的执行shiftDown操作,判断条件是 data[k] 有孩子
        //现在需要将 data[k] 的孩子中找出最大值,与 data[k]交换位置
        while (2 * k <= count) {
            int j = 2 * k;  //表示此轮循环中, data[k] 要和 data[j] 交换位置
            //如果它有右孩子并且右孩子比左孩子大,那么就要更新 j ,一会交换 data[k] 与 data[j+1] 的位置
            if (2 * k + 1 <= count && data[j + 1] > data[j]) {
                j += 1;
            }
            //如果 data[k] 比即将交换位置的值(子树中的最大值)要大,证明现在已经是最大堆了,退出循环
            if (data[k] >= data[j]) {
                break;
            }
            //交换 data[k] 与 data[j]
            int temp = data[k];
            data[k] = data[j];
            data[j] = temp;
            //更新 k 的位置,在进行新一轮的交换,直到整个结构满足最大堆的性质
            k = j;
        }
    }

    public int getCount() {
        return count;
    }

    public boolean isEmpty() {
        return count == 0;
    }


    //插入新的元素
    public void insert(int item) {

        //防止数组越界
        assert count + 1 <= num;
        //将新加入的数据放在堆的末尾,然后使用完全二叉树的性质进行排序
        data[count + 1] = item;
        count++;
        shiftUp(count);
    }

    //删除最大的节点,即删除 data[1],然后使整个二叉树仍然保持最大堆的性质
    public int extrackMax() {
        assert count > 0;
        //删除节点时,首先将最后一个元素 (data[count]) 覆盖掉第一个节点,然后通过 shiftDown 函数使整个二叉树满足最大堆
        int item = data[1];
        data[1] = data[count];
        count--;
        shiftDown(1);
        return item;
    }

    public int[] sortInside() {
        //将已经得到的最大堆的第一个值 (data[1])与最后一个值进行交换,然后执行ShiftDown操作,保证它依旧是个最大堆就好
        for (int i = 1; i <= num; i++) {
            //交换data[1] 与 data[count] 的位置
            int temp = data[1];
            data[1] = data[count];
            data[count] = temp;
            count--;
            shiftDown(1);
        }

        return data;
    }

    public MaxHeap(int num) {
        data = new int[num + 1];
        this.count = 0;
        this.num = num;
    }

    public MaxHeap(int[] arr) {
        data = new int[arr.length + 1];
        this.num = arr.length;
        //这里不在插入数据时保证最大堆
        for (int i = 0; i < num; i++) {
            data[i + 1] = arr[i];
        }
        count = num;
        //从第一个拥有子节点的节点( arr[count / 2] )开始进行shiftDown操作,逐渐往上遍历
        for (int i = count / 2; i >= 1; i--) {
            shiftDown(i);
        }
    }
}