Skip to main content
 首页 » 编程设计

详解Java 堆排序

2022年07月19日137TianFang

详解Java 堆排序

本文我们学习Java中如何实现堆排序。堆排序基于堆数据结构,为了更好地理解堆排序,我们首先深入堆数据结构及其实现。

1. 堆数据结构

堆是特殊的基于树的数据结构。因此其由节点组成,给节点赋值元素,每个节点恰好包括一个元素。节点能有子节点,没有任何子节点的节点为叶子节点。堆的特殊之处有两点规则:

  1. 每个节点值必须小于等于所有子节点的值
  2. 堆是完全树,即其高度最小

有第一条规则得到最小元素总是树的根节点。如何实现这些规则取决于实现。
堆通常用于实现优先队列,因为抽取最小或最多元素的实现非常有效。

1.1. 堆变体

堆有很多变体,主要差异体现在实现细节上。例如上面描述的最小堆,父节点总是小于其所有子节点。同样,我们也能定义最大堆,即父节点总是大于其子节点,因此最大元素是根节点。

可以选择多种树的实现,最直接是二叉树。二叉树每个节点最多有两个子节点,称为左节点和右节点。

执行第二条规则最简单方式是使用完全二叉树。完全二叉树符合下面简单规则:

  1. 如果节点有一个子节点,应该为左子节点
  2. 只有最底层最右边的节点可以有一个子节点
  3. 叶子节点只能在最深级

下面看一些示例检验这些规则:

 
1        2      3        4        5        6         7         8        9       10 
()       ()     ()       ()       ()       ()        ()        ()       ()       () 
        /         \     /  \     /  \     /  \      /  \      /        /        /  \ 
       ()         ()   ()  ()   ()  ()   ()  ()    ()  ()    ()       ()       ()  () 
                               /          \       /  \      /  \     /        /  \ 
                              ()          ()     ()  ()    ()  ()   ()       ()  () 
                                                                            / 
                                                                           () 

1、2、4、5、7符合以上规则。
3和6违反第一条规则,8和9违反第二条规则,10不符合第三条规则。接下来主要聚集基于二叉树实现最小堆。

1.2. 插入元素

应该基于一种方式实现插入操作,始终保持堆不变。基于此通过重复执行插入操作构件堆。所以我们看单个插入操作。插入一个元素的步骤为:

  1. 创建一个叶子节点作为树最深级上最右边节点并存储元素至节点中
  2. 如何元素小于父节点,则交换两个节点值
  3. 继续第二步,直到元素小于其父节点或该节点称为新的根节点

注意,第二步不违反堆规则,因为如果使用最小值交换,直到父节点成为所有子节点的最小值。请看示例,插入4至堆中:

 
     2 
    / \ 
   /   \ 
  3     6 
 / \ 
5   7 

第一步创建叶子节点存储4:

     2 
    / \ 
   /   \ 
  3     6 
 / \   / 
5   7 4 

4小于父节点6,需要交换:

     2 
    / \ 
   /   \ 
  3     4 
 / \   / 
5   7 6 

现在检测4是否小于其父节点,父节点为2,停止交换插入完毕,为有效堆。下面插入1:

     2 
    / \ 
   /   \ 
  3     4 
 / \   / \ 
5   7 6   1 

交换1和4:

     2 
    / \ 
   /   \ 
  3     1 
 / \   / \ 
5   7 6   4 

继续交换1和2:

     1 
    / \ 
   /   \ 
  3     2 
 / \   / \ 
5   7 6   4 

1为新的根节点,插入完成。

2. Java实现堆

我们使用完全二叉树,可以使用数组实现。数组中的元素作为树节点。使用数组索引从左到右标记每个节点,从顶到底遵循下列方式:

     0 
    / \ 
   /   \ 
  1     2 
 / \   / 
3   4 5 

我们唯一需要做的是跟踪我们在树中存储了多少元素。这样,我们要插入的下一个元素的索引将是数组的大小。使用索引可以计算父节点和子节点的索引:

  • 父节点: (index – 1) / 2
  • 左子节点: 2 * index + 1
  • 右子节点: 2 * index + 2

如果不想总是重建数组,可以简化实现直接使用ArrayList。基于二叉树实现如下:

class BinaryTree<E> { 
  
    List<E> elements = new ArrayList<>(); 
  
    void add(E e) { 
        elements.add(e); 
    } 
  
    boolean isEmpty() { 
        return elements.isEmpty(); 
    } 
  
    E elementAt(int index) { 
        return elements.get(index); 
    } 
  
    int parentIndex(int index) { 
        return (index - 1) / 2; 
    } 
  
    int leftChildIndex(int index) { 
        return 2 * index + 1; 
    } 
  
    int rightChildIndex(int index) { 
        return 2 * index + 2; 
    } 
  
} 

上面代码仅增加元素至树末尾。因此如果需要向上遍历新元素,使用下面代码实现:

class Heap<E extends Comparable<E>> { 
  
    // ... 
  
    void add(E e) { 
        elements.add(e); 
        int elementIndex = elements.size() - 1; 
        while (!isRoot(elementIndex) && !isCorrectChild(elementIndex)) { 
            int parentIndex = parentIndex(elementIndex); 
            swap(elementIndex, parentIndex); 
            elementIndex = parentIndex; 
        } 
    } 
  
    boolean isRoot(int index) { 
        return index == 0; 
    } 
  
    boolean isCorrectChild(int index) { 
        return isCorrect(parentIndex(index), index); 
    } 
  
    boolean isCorrect(int parentIndex, int childIndex) { 
        if (!isValidIndex(parentIndex) || !isValidIndex(childIndex)) { 
            return true; 
        } 
  
        return elementAt(parentIndex).compareTo(elementAt(childIndex)) < 0; 
    } 
  
    boolean isValidIndex(int index) { 
        return index < elements.size(); 
    } 
  
    void swap(int index1, int index2) { 
        E element1 = elementAt(index1); 
        E element2 = elementAt(index2); 
        elements.set(index1, element2); 
        elements.set(index2, element1); 
    } 
      
    // ... 
  
} 

需要对元素进行比较,故实现java.util.Comparable接口。

3. 堆排序

因为堆根元素总是最小元素,堆排序实现思路非常简单:删除根节点直到堆为空。

我们唯一需要实现的是删除操作,需始终保持堆的状态一致,确保不违反二叉树的结构,即堆的特性。

为了保持结构,每次删除根节点元素,并存储最右边的叶子节点至根节点。但该操作很可能违反堆属性,因为如果新根节点大于任何子节点,需要和最小子节点进行交换。最小子节点是所有其他子节点中最小的,所有不会违反堆属性。
一直交换直到元素成为叶子节点或小于所有子节点。请看示例:

     1 
    / \ 
   /   \ 
  3     2 
 / \   / \ 
5   7 6   4 

放最后元素在根节点上:

     4 
    / \ 
   /   \ 
  3     2 
 / \   / 
5   7 6 

4大于两个子节点,需要和两者最小的进行交换,即2:

     2 
    / \ 
   /   \ 
  3     4 
 / \   / 
5   7 6 

4小于6,操作结束。

3.1. 堆排序实现

利用前节代码,删除根节点方法(pop)如下:

class Heap<E extends Comparable<E>> { 
  
    // ... 
  
    E pop() { 
        if (isEmpty()) { 
            throw new IllegalStateException("You cannot pop from an empty heap"); 
        } 
  
        E result = elementAt(0); 
  
        int lasElementIndex = elements.size() - 1; 
        swap(0, lasElementIndex); 
        elements.remove(lasElementIndex); 
  
        int elementIndex = 0; 
        while (!isLeaf(elementIndex) && !isCorrectParent(elementIndex)) { 
            int smallerChildIndex = smallerChildIndex(elementIndex); 
            swap(elementIndex, smallerChildIndex); 
            elementIndex = smallerChildIndex; 
        } 
  
        return result; 
    } 
      
    boolean isLeaf(int index) { 
        return !isValidIndex(leftChildIndex(index)); 
    } 
  
    boolean isCorrectParent(int index) { 
        return isCorrect(index, leftChildIndex(index)) && isCorrect(index, rightChildIndex(index)); 
    } 
      
    int smallerChildIndex(int index) { 
        int leftChildIndex = leftChildIndex(index); 
        int rightChildIndex = rightChildIndex(index); 
          
        if (!isValidIndex(rightChildIndex)) { 
            return leftChildIndex; 
        } 
  
        if (elementAt(leftChildIndex).compareTo(elementAt(rightChildIndex)) < 0) { 
            return leftChildIndex; 
        } 
  
        return rightChildIndex; 
    } 
      
    // ... 
  
} 

如前面分析,排序是通过不断删除根节点从新创建一个堆:

class Heap<E extends Comparable<E>> { 
  
    // ... 
  
    static <E extends Comparable<E>> List<E> sort(Iterable<E> elements) { 
        Heap<E> heap = of(elements); 
  
        List<E> result = new ArrayList<>(); 
  
        while (!heap.isEmpty()) { 
            result.add(heap.pop()); 
        } 
  
        return result; 
    } 
      
    static <E extends Comparable<E>> Heap<E> of(Iterable<E> elements) { 
        Heap<E> result = new Heap<>(); 
        for (E element : elements) { 
            result.add(element); 
        } 
        return result; 
    } 
      
    // ... 
  
} 

我们能测试是否正确:

@Test 
void givenNotEmptyIterable_whenSortCalled_thenItShouldReturnElementsInSortedList() { 
    // given 
    List<Integer> elements = Arrays.asList(3, 5, 1, 4, 2); 
      
    // when 
    List<Integer> sortedElements = Heap.sort(elements); 
      
    // then 
    assertThat(sortedElements).isEqualTo(Arrays.asList(1, 2, 3, 4, 5)); 
} 

请注意,我们可以提供另一个就地排序实现,这意味着只用一个数组获得结果。通过这种方式不需要任何中间内存分配。但这种实现可能比较难以理解。

3.2. 时间复杂度

堆排序由两个关键步骤,插入元素和删除根节点。两个步骤的实际复杂度都为O(log n)。因为需要重复两个步骤n次,整个排序复杂度为O(n log n)。

我们没有提到数组重新分配的成本,但是因为它是O(n),所以它不会影响整体的复杂性。另外,正如我们前面提到的,可以实现就地排序,这意味着不需要重新分配数组。同样值得一提的是,50%的元素是叶子,75%的元素位于两个最下面的层次。因此,大多数插入操作只需要两个步骤。

注意,在实际数据中,快速排序通常比堆排序性能更好。最坏情况下,堆排序的时间复杂度总是O(n log n)。

4. 总结

本文我们介绍了堆数据结构及其实现。因为其时间复杂度为O(n log n),实际上并不是最好的排序算法,但在优先队列场景中经常使用。


本文参考链接:https://blog.csdn.net/neweastsun/article/details/104100856
阅读延展