Java实现最大(小)堆以及堆排序、TopN问题

Java实现最大(小)堆以及堆排序、TopN问题

文章目录


Java实现堆

什么是堆,先来了解原理,再看如何实现。

  • 堆的定义:堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。

堆可以看成是一棵树,并且这棵树的子树也是堆。而最大堆就是父节点大于子节点,根节点是最大的节点;最小堆就是父亲节点小于子节点,根节点是最小的节点。

要注意堆和二叉查找树的区别,二叉查找树是左子节点比父节点小,右子节点比父节点大。

如图最大堆、最小堆:

Java实现最大(小)堆以及堆排序、TopN问题

而我们知道二叉树有一条性质是:
当前节点下标与子节点下标存在着这样的关系:左子节点的下标等于父节点的两倍,右子节点的下标等于父节点的两倍加1,即left_son.index = current.index * 2right_son.index = current.index * 2 + 1

而这个二叉树又是一个完全二叉树,结合上面这个特性,那么利用数组实现堆是十分合适的。

下面步入正题,堆的构建:

堆的构建

给定一个数组{1,9,7,5,18,4},对应的二叉树如下:

Java实现最大(小)堆以及堆排序、TopN问题

我们需要把它调整成最大堆,也就是堆的初始化过程:可以从上往下,也可以从下往上,但是从上往下每次都要将子树遍历完,重复遍历了很多节点。所以采用自底向上方法,即从最后一个有子节点的开始(因为它是最后一个节点的父节点,所以它的下标是size / 2),让它的两个子节点进行比较,找到大的值再和父节点的值进行比较。如果父结点的值小,则子结点和父结点进行交换,交换之后再递归往下比较。然后再一步步递归上去,直到根节点结束。

7是最后一个有子节点的节点,和左右儿子节点比较,然后和大的换位子,然后先往下递归重复这个步骤到比它小的节点,然后再向上递归重复这个步骤到根节点,这里7是最大的,不用换,然后递归到上一层,即17比较,具体过程如下:

Java实现最大(小)堆以及堆排序、TopN问题

实现代码:

    /**
     * 构造函数
     */
    public MaxHeap(int[] num, int capacity) {
        this(capacity + 1);
        if (num.length > capacity) {
            try {
                throw new Exception("capacity不能小于数组的长度!");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        for (int i = 1, len = num.length; i <= len; ++i) {
            ++size;
            heap[i] = num[i - 1];
        }
        adjustment(); // 调整堆
    }

    /**
     * 调整堆
     */
    private void adjustment() {
        for (int i = size / 2; i >= 1; --i) {
            int temp = heap[i]; // 当前操作的节点,从后往前,第一个操作的就是那个有子节点的节点
            int max_index = i * 2; // 当前节点的左儿子节点
            while (max_index <= size) { // 当前节点的左儿子节点有效,下标在1~size代表有效
                if (max_index < size && heap[max_index] < heap[max_index + 1])
                    ++max_index;
                if (temp > heap[max_index]) break;
                heap[max_index / 2] = heap[max_index];
                max_index *= 2;
            }
            heap[max_index / 2] = temp;
        }
    }

堆的插入

最大堆的插入: 将元素插入末尾,因为原本已经是最大堆了,所以只需层层向上比较即可,比如上图,我要插入10,只需要和7比较,然后和18比较即可。

Java实现最大(小)堆以及堆排序、TopN问题

实现代码:

    public void insert(int element) {
        if (size == 0) { // 堆为空,直接插入0位置
            heap[1] = element;
            ++size;
        } else if (size >= heap.length - 1) { // 容量已满,抛出异常
            try {
                throw new Exception("容量已满!");
            } catch (Exception e) {
                e.printStackTrace();
            }
        } else {
            int index = ++size; // index即为新插入元素的下标
            while (index != 1 && element > heap[index / 2]) {
                // 一直向上找,直到找到一个比插入元素大的节点,或者到了根节点
                heap[index] = heap[index / 2];
                index /= 2;
            }
            heap[index] = element;
        }
    }

堆的删除

删除根节点: 这就更简单了,直接将最后一个节点移到根节点,然后再调整堆,即上面的构建过程。

实现代码:

    public int removeMax() {
        int max = heap[1];
        heap[1] = heap[size--];
        adjustment();
        return max;
    }

具体实现代码

详细实现代码(我写的比较特殊,只能存int,可以根据自己的需要添加泛型class MaxHeap<T extends Comparable<T>>,即堆可存储自定义的类型元素,但是要实现了Comparable接口的,然后用compareTo方法替换掉大于小于号,int换成T):

package com.au.sql;

public class MaxHeap {
    private int[] heap; // 数组
    private int size; // 实际存数据的个数
    private final static int DEFAULT_CAPACITY = 100; // 默认堆容量

    /**
     * 多个构造函数是为了满足不同的需要
     */
    public MaxHeap() {
        this(DEFAULT_CAPACITY);
    }

    public MaxHeap(int capacity) {
        heap = new int[capacity + 1];
        size = 0;
    }

    public MaxHeap(int[] num) {
        this(num, num.length * 2);
    }

    public MaxHeap(int[] num, int capacity) {
        this(capacity + 1);
        if (num.length > capacity) {
            try {
                throw new Exception("capacity不能小于数组的长度!");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        for (int i = 1, len = num.length; i <= len; ++i) {
            ++size;
            heap[i] = num[i - 1];
        }
        adjustment(); // 调整堆
    }

    /**
     * 调整堆
     */
    private void adjustment() {
        for (int i = size / 2; i >= 1; --i) {
            int temp = heap[i]; // 当前操作的节点,从后往前,第一个操作的就是那个有子节点的节点
            int max_index = i * 2; // 当前节点的左儿子节点
            while (max_index <= size) { // 当前节点的左儿子节点有效,下标在1~size代表有效
                if (max_index < size && heap[max_index] < heap[max_index + 1])
                    ++max_index;
                if (temp > heap[max_index]) break;
                heap[max_index / 2] = heap[max_index];
                max_index *= 2;
            }
            heap[max_index / 2] = temp;
        }
    }

    public void insert(int element) {
        if (size == 0) { // 堆为空,直接插入0位置
            heap[1] = element;
            ++size;
        } else if (size >= heap.length - 1) { // 容量已满,抛出异常
            try {
                throw new Exception("容量已满!");
            } catch (Exception e) {
                e.printStackTrace();
            }
        } else {
            int index = ++size; // index即为新插入元素的下标
            while (index != 1 && element > heap[index / 2]) {
                // 一直向上找,直到找到一个比插入元素大的节点,或者到了根节点
                heap[index] = heap[index / 2];
                index /= 2;
            }
            heap[index] = element;
        }
    }

    /**
     * 删除最大值
     *
     * @return
     */
    public int removeMax() {
        int max = heap[1];
        heap[1] = heap[size--];
        adjustment();
        return max;
    }

    public void print() {
        for (int i = 1; i <= size; ++i) {
            System.out.print(heap[i] + " ");
        }
    }

    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap();
        maxHeap.insert(12);
        maxHeap.insert(14);
        maxHeap.insert(11);
        maxHeap.insert(110);
        maxHeap.insert(411);
        maxHeap.insert(11);
        maxHeap.print();
        System.out.println();
        System.out.println("============");
        MaxHeap maxHeap1 = new MaxHeap(new int[]{12, 14, 11, 110, 411, 11});
        maxHeap1.removeMax();
        maxHeap1.print();


    }
}

堆排序

了解了堆的原理,堆排序应该很简单了,我们只需要将最后一个节点与第一个节点交换即可,换完一个size1,然后调整堆,然后循环这个步骤,直到换完。

实现代码(利用上面的代码):

    public void heapSort() {
        int temp = size; // 先把原大小存一下
        for (int i = size; i > 0; --i) {
            --size;
            int t = heap[i];
            heap[i] = heap[1];
            heap[1] = t;
            adjustment();
        }
        size = temp;
    }

TopN问题

这个就更加简单了,维护一个N就行了。

    public int topN(int n) {
        int temp = size; // 先把原大小存一下
        int res = 0;
        for (int i = size; i > 0; --i) {
            if (--n == 0) {
                res = heap[1];
                break;
            }
            --size;
            int t = heap[i];
            heap[i] = heap[1];
            heap[1] = t;
            adjustment();
        }
        size = temp;
        return res;
    }
上一篇:Flink SQL 功能解密系列 —— 流式 TopN 挑战与实现


下一篇:Python 连接SQLite数据库 及基础操作