堆排序

发表于 | 分类于 | 阅读次数:

堆排序使用的是二叉堆。首先将所有的元素添加到一个堆上，然后不断移除最大的元素以获得一个排好序的线性表。

堆的存储

堆排序(heap sort)使用二叉堆(binary heap)，它是一棵 完全二叉树，每个节点大于或等于它的任意一个孩子。
如果一颗二叉树的每一层都是满的，或者最后一层可以不填满并且最后一层的叶子都是靠左放置的，那么这棵二叉树就是完全的(complete)。
如果堆的大小是事先知道的，那么可将堆存储在一个ArrayList或一个数组中。树根在位置0处，它的两个子节点在位置1和位置2处。

对于位置i处的节点，它的：

  • 左子结点在位置 2i+1 处
  • 右子结点在位置 2i+2 处
  • 父节点在位置 (i-1)/2 处

添加一个新结点

给堆添加一个新结点，首先将它添加到堆的末尾，然后按如下方式重建这棵树：

Adding a New Node Psuedo Code
1
2
3
4
5
6
7
8
9
10
11
12
Let the last node be the current node;
while (the current node is greater than its parent) {
    Swap the current node with its parent;
    Now the current node is one level up;
}


令最后一个节点的那个做当前节点;
while (当前节点大于他的父节点) {
    将当前节点和它的父节点交换;
    现在当前节点往上面进了一个层级;
}

删除一个结点

经常需要从堆中删除最大的元素，也就是这个堆中的根节点。在删除根节点之后，就必须重建这棵树以保持堆的属性。重建该树的算法如下所示：

Removing the Root Psuedo code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Move the last node to replace the root;
Let the root be the current node;
while (the current node has childen && the current node is 
       smaller than one of its children) {
    Swap the current node with the larger of its children;
    Now the current node is one level down;
    }


用最后一个节点替换根节点;
让根节点成为当前节点;
while (当前节点具有子节点&&当前节点小于它的子节点) {
    将当前节点和它的较大子节点交换;
    现在当前节点往下面退了一个层次;
}

Heap类

Comparable可以认为是一个内比较器，实现了Comparable接口的类有一个特点，就是这些类是可以和自己比较的，至于具体和另一个实现了Comparable接口的类如何比较，则依赖compareTo方法的实现，compareTo方法也被称为自然比较方法。如果开发者进入一个Collection的对象想要Collections的sort方法帮你自动进行排序的话，那么这个对象必须实现Comparable接口。compareTo方法的返回值是int，有三种情况：

  1. 比较者大于被比较者（也就是compareTo方法里面的对象），那么返回正整数
  2. 比较者等于被比较者，那么返回0
  3. 比较者小于被比较者，那么返回负整数

Comparator可以认为是是一个外比较器，个人认为有两种情况可以使用实现Comparator接口的方式：
1)一个对象不支持自己和自己比较（没有实现Comparable接口），但是又想对两个对象进行比较;2)一个对象实现了Comparable接口，但是开发者认为compareTo方法中的比较方式并不是自己想要的那种比较方式
Comparator接口里面有一个compare方法，方法有两个参数T o1和T o2，是泛型的表示方式，分别表示待比较的两个对象，方法返回值和Comparable接口一样是int，有三种情况：

  1. o1大于o2，返回正整数
  2. o1等于o2，返回0
  3. o1小于o3，返回负整数

使用Comparable接口对元素排序

使用Comparable接口对元素排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.Comparator;
import java.util.ArrayList;

public class Heap<E extends Comparabel<E>> {
    private ArrayList<E> list = new ArrayList<>();
    public Heap() {}
    public Heap(E[] objects) {
        for (int i = 0; i < objects.length; i++) {
            this.add(objects[i]);
        }
    }
    public void add(E newObject) {
        list.add(newObject);
        int currentIndex = list.size() - 1;
        while (currentIndex > 0) {
            int parentIndex = (currentIndex - 1) / 2;
            if (list.get(currentIndex).compareTo(list.get(parentIndex)) > 0) {
                E tmp = list.get(currentIndex);
                list.set(currentIndex, list.get(parentIndex));
                list.set(parentIndex, tmp);
            } else {
                break;
            }
            currentIndex = parentIndex;
        }
    }
    public E remove() {
        if (list.size() == 0)
            return null;
        E removeObject = list.get(0);
        list.set(0, list.get(list.size() - 1));
        list.remove(list.size() - 1);

        int currentIndex = 0;
        while (currentIndex < list.size()) {
            int leftChildIndex = 2 * currentIndex + 1;
            int rightChildIndex = 2 * currentIndex + 2;
            if (leftChildIndex >= list.size())
                break;
            int maxIndex = leftChildIndex;
            if (rightChildIndex < list.size()) {
                if (list.get(maxIndex).comparetTo(list.get(rightChildIndex)) < 0) {
                    maxIndex = rightChildIndex;
                }
            }
            if (list.get(currentIndex).compareTo(list.get(maxIndex)) < 0) {
                E tmp = list.get(maxIndex);
                list.set(maxIndex, list.get(currentIndex));
                list.set(currentIndex, tmp)
            } else {
                break;
            }
            currentIndex = maxIndex;
        }
        return removeObject;
    }
    public int getSize() {
        return list.size();
    }
}

使用Comparator接口对元素排序

使用Comparator接口对元素排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.ArrayList;
import java.util.Comparator;
public class HeapA<E> {
    private Comparator<? super E> comparator;
    private ArrayList<E> list = new ArrayList<>();

    public HeapA(Comparator<? super E> comparator) {
        this.comparator = comparator;
    }
    public void add(E newObject) {
        list.add(newObject);
        int currentIndex = list.size() - 1;
        while (currentIndex > 0) {
            int parentIndex = (currentIndex - 1) / 2;
            if (comaprator.compare(list.get(currentIndex), list.getIparentIndex)) > 0) {
                E tmp = list.get(currentIndex);
                list.set(currentIndex, list.get(parentIndex));
                list.set(parentIndex, tmp);
            } else {
                break;
            }
            currentIndex = parentIndex;
        }
    }
    pubic E remove() {
        if (list.size() == 0) return null;
        E removeObject = list.get(0);
        list.set(0, list.get(list.size() - 1));
        list.remove(list.size() - 1);

        int currentIndex = 0;
        while (currentIndex < list.size()) {
            int leftChildIndex = 2 * currentIndex + 1;
            int rightChildIndex = 2 * currentIndex + 2;
            //这里是大于等于
            if (leftChildIndex >= list.size())
                break;
            int maxIndex = leftChildIndex;
            if(rigthChildIndex < list.size()) {
                if (comparator.compare(list.get(maxIndex), list.get(rightChildIndex)) < 0) {
                    maxIndex = rightChildIndex;
                }
            }
            if (comparator.compare(list.get(currentIndex), list.get(maxIndex)) < 0) {
                E tmp = list.get(maxIndex);
                list.set(maxIndex, list.get(currentIndex));
                list.set(currentIndex, tmp);
            } else {
                break;
            }
            currentIndex = maxIndex;
        }
        return removeObject;
    }
    pubic int getSize() {
        return list.size();
    }
}

使用Heap类进行排序

使用Comparator需要编写测试用例，实现Comparator接口的的GeomatricObjectComparator，以及抽象父类GeometricObject,抽象方法getArea，在子类Circle和Rectangle类中实现。排序算法为HeapSort。

HeapSort排序算法

HeapSort排序算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import java.util.Comparator;

public class HeapSort {
    public static <E extends Comparable<E>> void heapSort(E[] list) {
        Heap<E> heap = new Heap<>();
        for (int i = 0; i < list.length; i++) {
            heap.add(list[i]);
        }
        for (int i = list.length - 1; i >= 0; i--) {
            list[i] = heap.remove();
        }
    }
    public static <E> void heapSort(E[] list, Comparator<? super E> comparator) {
        HeapA<E> heap = new HeapA<>(comparator);
        for (int i = 0; i < list.length; i++) {
            heap.add(list[i]);
        }
        for (int i = list.length - 1; i >= 0; i--) {
            list[i] = heap.remove();
        }
    }       
    
    public static void main(String[] args) {
        /** Create an Array of Integers */
        Integer[] intArray = {-44, -5, -3, 3, 3, 1, -4, 0, 1, 2, 4, 5, 53};
        
        /** Create an Array of Doubles */
        Double[] doubleArray = {3.4, 1.3, -22.1, 14.8, 6.0, 2.3, 12.2};
        
        /** Create an Array of Characters */
        Character[] charArray = {'a', 'J', 'r'};
        
        /** Create an Array of String */
        String[] stringArray = {"Tom", "Susan", "Kim"};
        
        /** Heapsort the arrays */
        heapSort(intArray);
        heapSort(doubleArray);
        heapSort(charArray);
        heapSort(stringArray);
        
        /** Display the array */
        System.out.print("Sorted Integers: ");
        printList(intArray);
        
        System.out.print("Sorted Doubles: ");
        printList(doubleArray);

        System.out.print("Sorted Characters: ");
        printList(charArray);

        System.out.print("Sorted Strings: ");
        printList(stringArray);
        
        GeometricObject[] list = {new Circle(5), new Rectangle(4, 5),
            new Circle(5.5), new Rectangle(2.4, 5), new Circle(0.5), 
            new Rectangle(4, 65), new Circle(4.5), new Rectangle(4.4, 1),
            new Circle(6.5), new Rectangle(4, 5)};
        
        heapSort(list, new GeometricObjectComparator());
        System.out.print("Sorted elements: ");
        for (GeometricObject e: list) {
            System.out.printf("%.2f ", e.getArea());
        }
        System.out.println();
    }
    
    public static void printList(Object[] list) {
        for (int i = 0; i < list.length; i++)
            System.out.print(list[i] + " ");
        System.out.println();
    }
}

GeometricObjectComparator类实现java.util.Comparator接口

GeometricObjectComparator类实现java.util.Comparator接口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.io.Serializable;
import java.util.Comparator;
public class GeometricObjectComparator implements Comparator<GeometricObject>, Serializable {  
   
    @Override
    public int compare(GeometricObject o1, GeometricObject o2) {
        // TODO Auto-generated method stub
        double area1 = o1.getArea();
        double area2 = o2.getArea();
        if (area1 < area2) {
            return -1;
        } else if (area1 == area2) {
            return 0;
        } else {
            return 1;
        }
    }

}

GeometricObject抽象父类

GeometricObject抽象父类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.util.Date;

public abstract class GeometricObject {
    private String color = "white";
    private boolean filled;
    private Date dateCreated;
    
    protected GeometricObject() {
        dateCreated = new Date();
    }
    protected GeometricObject(String color, boolean filled) {
        dateCreated = new Date();
        this.color = color;
        this.filled = filled;
    }
    /** Return color */
    public String getColor() {
        return color;
    }

    /** Set a new color */
    public void setColor(String color) {
        this.color = color;
    }

    /** Return filled. Since filled is boolean,
     *  the get method is named isFilled */
    public boolean isFilled() {
        return filled;
    }

    /** Set a new filled */
    public void setFilled(boolean filled) {
        this.filled = filled;
    }

    /** Get dateCreated */
    public java.util.Date getDateCreated() {
        return dateCreated;
    }

    @Override
    public String toString() {
        return "created on " + dateCreated + "\ncolor: " + color +
            " and filled: " + filled;
    }

    /** Abstract method getArea */
    public abstract double getArea();

    /** Abstract method getPerimeter */
    public abstract double getPerimeter();  
    
}

Circle类继承自GeometricObject

Circle类继承自GeometricObject
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Circle extends GeometricObject {
    private double radius;
    public Circle() {
    }
    public Circle(double radius) {
        this.radius = radius;
    }
    public Circle(double radius, 
        String color, boolean filled) {
        this.radius = radius;
        setColor(color);
        setFilled(filled);
    }

    
    public double getRadius() {
        return radius;
    }    
    public void setRadius(double radius) {
        this.radius = radius;
    }

    @Override 
    public double getArea() {
        return radius * radius * Math.PI;
    }    
    public double getDiameter() {
        return 2 * radius;
    }

    @Override 
    public double getPerimeter() {
        return 2 * radius * Math.PI;
    }
    @Override
    public String toString() {
        return super.toString() + ", Circle, Created: " 
            + getDateCreated() + ", Radius: " + radius;
    }
}

Rectangle类继承自GeometricObject

Rectangle类继承自GeometricObject
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class Rectangle extends GeometricObject {
    private double width;
    private double height;
    public Rectangle() {
    }
    public Rectangle(
        double width, double height) {
        this.width = width;
        this.height = height;
    }
    public Rectangle(
        double width, double height, String color, boolean filled) {
        this.width = width;
        this.height = height;
        setColor(color);
        setFilled(filled);
    }
    
    public double getWidth() {
        return width;
    }    
    public void setWidth(double width) {
        this. width = width;
    }    
    public double getheight() {
        return height;
    }    
    public void setheight(double height) {
        this.height = height;
    }

    @Override 
    public double getArea() {
        return width * height;
    }

    @Override 
    public double getPerimeter() {
        return 2 * (width * height);
    }

    @Override 
    public String toString() {
        return super.toString() + " Rectangle, Created: " 
            + getDateCreated() + ", Width: " + width + 
            ", Height: " + height;
    }
}

堆排序的时间复杂度

设h表示包含n个元素的堆的高度。 堆的高度为O(logn)。
由于add方法会追踪从叶子节点到根节点的路径，因此向堆中添加一个新元素最多需要h步。所以建立一个包含n个元素的数组的初始堆需要O(nlogn)时间。
由于remove方法要跟踪从根节点到叶子节点的路径，因此从堆中删除根节点后，重建堆最多需要h步。由于要调用n次remove方法，所以产生一个有序数组需要的总时间为O(nlogn)。
堆排序不需要额外的数组空间，空间效率高于归并排序。

实现clone和equals的堆方法

实现clone和equals方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
import java.util.Comparator;
import java.util.ArrayList;

public class Heap <E extends Comparable<E>> implements Cloneable{
    private ArrayList<E> list = new ArrayList<>();;

    /** Create a default heap */
    public Heap() {
    }

    /** Create a heap from an array of objects */
    public Heap(E[] objects) {
        for (int i = 0; i < objects.length; i++)
            add(objects[i]);
    }

    /** Add a new object into the heap */
    public void add(E newObject) {
        list.add(newObject); // Append to the heap
        int currentIndex = list.size() - 1; // The index of the last node

        while (currentIndex > 0) {
            int parentIndex = (currentIndex - 1) / 2;
            // Swap if the current object is greater than its parent
            if (list.get(currentIndex).compareTo(
                list.get(parentIndex)) > 0) {
                E temp = list.get(currentIndex);
                list.set(currentIndex, list.get(parentIndex));
                list.set(parentIndex, temp);
            }
            else
                break; // The tree is a heap now

            currentIndex = parentIndex;
        }
    }

    /** Remove the root from the heap */
    public E remove() {
        if (list.size() == 0) return null;

        E removedObject = list.get(0);
        list.set(0, list.get(list.size() - 1));
        list.remove(list.size() - 1);

        int currentIndex = 0;
        while (currentIndex < list.size()) {
            int leftChildIndex = 2 * currentIndex + 1;
            int rightChildIndex = 2 * currentIndex + 2;

            // Find the maximum between two children
            if (leftChildIndex >= list.size()) break; // The tree is a heap
            int maxIndex = leftChildIndex;
            if (rightChildIndex < list.size()) {
                if (list.get(maxIndex).compareTo(
                    list.get(rightChildIndex)) < 0) {
                    maxIndex = rightChildIndex;
                }
            }

            // Swap if the current node is less than the maximum
            if (list.get(currentIndex).compareTo(
                list.get(maxIndex)) < 0) {
                E temp = list.get(maxIndex);
                list.set(maxIndex, list.get(currentIndex));
                list.set(currentIndex, temp);
                currentIndex = maxIndex;
            }
            else
                break; // The tree is a heap
        }

        return removedObject;
    }

    /** Get the number of nodes in the tree */
    public int getSize() {
        return list.size();
    }


    @Override /** Override teh proctected clone method defined in
        the Object class, and stregthen its accessibility */
    public Object clone() throws CloneNotSupportedException {
        return super.clone();
    }


    @Override /** Override the equals method in the Object class */
    public boolean equals(Object other) {
        if (list.size() != ((Heap)(other)).getSize())
            return false;

        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) != ((Heap)(other)).list.get(i))
                return false;
        }       
        return true;
    }

}
0%