堆排序


题:如何操作效率最高
堆的特征是每个节点的值不大于其孩子节点的值。

假设现在有一个已经建好的堆。这时,需要把一个新元素加入进来,同时仍然保持着堆的性质,该如何操作效率最高?

源码HSort.java


package HSort;

public class HSort {
    private int[] lst;
    public HSort() {
        lst = new int[0];
    }
    private void heap(int k) {
        int s = k;
        int t = (s-1)/2;
        int tmp = lst[s];
        while (s>0) {
            int c = lst[t]-tmp;
            if (c<=0) {
                break;
            }
            else {
                lst[s] = lst[t];
                s = t;
                t = (t-1)/2;
            }
        }
        lst[s] = tmp;
    }
    public void insert(int x) {
        int s = lst.length;
        int[] tmp = new int[s+1];
        System.arraycopy(lst, 0, tmp, 0, lst.length);
        tmp[s] = x;
        lst = tmp;
        heap(s);
    }
    public String toString() {
        StringBuffer sb = new StringBuffer();
        for (int i=0; i<lst.length; i++) {
            sb.append(lst[i]+" ");
        }
        return sb.toString();
    }
    
    
    public static void main(String[] args) {
        int a[] = {80, 40, 30, 60, 90, 70, 10, 50, 20};
        HSort tri = new HSort();
        for (int i=0; i<a.length; i++) {
            tri.insert(a[i]);
        }
        System.out.println(tri);
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注