泛型堆排序

简介:
public static <C extends Comparable> void sort(C[] array) {
    if (null == array || 1 >= array.length) {
        return;
    }
    MinHeap<C> root = new MinHeap<>(array[0]);
    for (int i = 1; i < array.length; i++) {
        root.add(array[i]);
        //System.out.println(root.toString());
    }
    //System.out.println();
    for (int i = 0; i < array.length; i++) {
        array[i] = root.pop();
        //System.out.println(root.toString());
    }
}
static class MinHeap<C extends Comparable> {

    static final int CHILDREN_COUNT = 2;

    C value;

    MinHeap<C> parent;

    List<MinHeap<C>> children = new LinkedList<>();

    MinHeap(C value) {
        this.value = value;
    }

    @SuppressWarnings("unchecked")
    C pop() {
        C top = this.value;
        if (!this.children.isEmpty()) {
            int index = 0;
            C val = children.get(0).value;
            for (int i = 1; i < children.size(); i++) {
                if (val.compareTo(children.get(i).value) > 0) {
                    val = children.get(i).value;
                    index = i;
                }
            }
            this.value = children.get(index).value;
            for (MinHeap<C> child : children.get(index).children) {
                child.parent = this;
                children.add(child);
            }
            children.remove(index);
        } else {
            this.value = null;
        }
        return top;
    }

    @SuppressWarnings("unchecked")
    void add(C value) {
        if (children.size() < CHILDREN_COUNT) {
            MinHeap<C> newOne = new MinHeap(value);
            children.add(newOne);
            newOne.parent = this;
            newOne.adjust();
        } else {
            int index = 0;
            int count = children.get(0).children.size();
            for (int i = 1; i < children.size(); i++) {
                if (children.get(i).children.size() < count) {
                    count = children.get(i).children.size();
                    index = i;
                }
            }
            children.get(index).add(value);
        }
    }

    @SuppressWarnings("unchecked")
    private void adjust() {
        if (null != parent && this.value.compareTo(parent.value) < 0) {
            swap(parent, this);
            parent.adjust();
        }
    }

    private void swap(MinHeap<C> parent, MinHeap<C> child) {
        C temp = parent.value;
        parent.value = child.value;
        child.value = temp;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(this.value);
        if (!this.children.isEmpty()) {
            builder.append("{ ");
            for (MinHeap<C> child : children) {
                builder.append(child.toString()).append(", ");
            }
            builder.append(" }");
        }
        return builder.toString();
    }
}
目录
相关文章
|
6月前
|
搜索推荐 Java 大数据
Java实现冒泡排序
Java实现冒泡排序
48 0
|
6月前
|
搜索推荐 Java
java实现冒泡排序和快速排序代码
java实现冒泡排序和快速排序
52 1
|
搜索推荐 C++ 容器
(C/C++)STL函数和排序算法:快排以及归并排序
(C/C++)STL函数和排序算法:快排以及归并排序
(C/C++)STL函数和排序算法:快排以及归并排序
泛型栈和队列
泛型栈和队列
118 0
|
搜索推荐 算法 Java
【排序算法】Java实现9大排序算法及其速度对比(附详细代码)
【排序算法】Java实现9大排序算法及其速度对比(附详细代码)
114 0
|
存储 算法 搜索推荐
STL常用排序算法
STL常用排序算法
STL常用排序算法
|
Java
冒泡排序(Java实现)
冒泡排序(Java实现)
117 0
冒泡排序(Java实现)
排序方法、其他常用的方法
快速排序 function fast (arr) { if (arr.length <= 1) { return arr } let left = [] let right = [] let p = arr.
606 0