泛型堆排序

简介:
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();
    }
}
目录
相关文章
|
5月前
|
存储 算法 搜索推荐
【数据结构】归并排序的非递归写法和计数排序
【数据结构】归并排序的非递归写法和计数排序
|
6月前
|
搜索推荐 Java
java实现冒泡排序和快速排序代码
java实现冒泡排序和快速排序
53 1
|
11月前
|
算法
insertionSoft(插入排序) 2.1-1 And 重写insertionSoft 2.1-2
insertionSoft(插入排序) 2.1-1 And 重写insertionSoft 2.1-2
34 0
|
算法 Java
java实现基数排序
java实现基数排序
47 0
|
存储 搜索推荐 测试技术
数据结构__<八大排序> __插入排序 |希尔排序 |选择排序 |堆排序 |快速排序 |归并排序(C语言实现)
数据结构__<八大排序> __插入排序 |希尔排序 |选择排序 |堆排序 |快速排序 |归并排序(C语言实现)
272 0
java实现数组二分查找
java实现数组二分查找
|
搜索推荐 索引
|
Java
Java实现基数排序
Java实现基数排序
119 0
Java实现基数排序
|
搜索推荐 C++ 容器
(C/C++)STL函数和排序算法:快排以及归并排序
(C/C++)STL函数和排序算法:快排以及归并排序
(C/C++)STL函数和排序算法:快排以及归并排序