5.13. Optimized heap sorting

发布时间 ： 2025-10-25 13:35:41 UTC      

Page Views: 35 views

In the heap sorting in the previous section, we opened up additional space to construct and sort the heap. In this section, we optimize using in-situ heap sorting.

For a maximum heap, first exchange the starting position data with the value at the end of the array, then the end of the array is the largest element, then shift down the W element to regenerate the maximum heap, and then swap the newly generated maximum number with the penultimate position of the entire array, which is the penultimate big data everywhere, and so on.

The whole process can be shown in the following figure:

image0

5.13.1. Java instance code

源码包下载： Download

Src/runoob/heap/HeapSort.java file code: 

package runoob.heap;
import runoob.sort.SortTestHelper;
/*\*
 \* 原地堆排序
 */
public class HeapSort {
    public static void sort(Comparable[] arr) {
        int n = arr.length;
        // 注意，此时我们的堆是从0开始索引的
        // 从(最后一个元素的索引-1)/2开始
        // 最后一个元素的索引 = n-1
        for (int i = (n - 1 - 1) / 2; i >= 0; i--)
            shiftDown(arr, n, i);

        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);
            shiftDown(arr, i, 0);
        }
    }
    // 交换堆中索引为i和j的两个元素
    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    // 原始的shiftDown过程
    private static void shiftDown(Comparable[] arr, int n, int k) {
        while (2 \* k + 1 < n) {
            //左孩子节点
            int j = 2 \* k + 1;
            //右孩子节点比左孩子节点大
            if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0)
                j += 1;
            //比两孩子节点都大
            if (arr[k].compareTo(arr[j]) >= 0) break;
            //交换原节点和孩子节点的值
            swap(arr, k, j);
            k = j;
        }
    }
    // 测试 HeapSort
    public static void main(String[] args) {
        int N = 100;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0,
100000);
        sort(arr);
        // 将heapify中的数据逐渐使用extractMax取出来
        // 取出来的顺序应该是按照从大到小的顺序取出来的
        for (int i = 0; i < N; i++) {
            System.out.print(arr[i] + " ");
        }
        // 确保arr数组是从大到小排列的
        for (int i = 1; i < N; i++)
            assert arr[i - 1] >= arr[i];
    }
}
      
                    
                
                

                    

                        

                            
                                文章链接
                            
                            ：
                            5.13. Optimized heap sorting 
                        

                    

                

            
        
        

            

    
        

            

                

                    
                        
                        
                            
Principles and Applications of WebGIS 

                        
                        
                             37
                        
                    
                    
                        

                            
 
 
 

                        

                    
                

                
            

        

    

    
        

            

                

                    
                        
                        
                            
Web框架 

                        
                        
                             942
                        
                    
                    
                        

                            
 
 
 

                        

                    
                

                
            

        

    

    
        

            

                

                    
                        
                        
                            
WEB基础 

                        
                        
                             287
                        
                    
                    
                        

                            
 
 
 

                        

                    
                

                
            

        

    

    
        

            

                

                    
                        
                        
                            
Principles, Technologies, and Methods of Geographic Information Systems 

                        
                        
                             102
                        
                    
                    
                        

                            
 
 
 In recent years, Geographic Information Systems (GIS) have undergone rapid development in both theoretical and practical dimensions. GIS has been widely applied for modeling and decision-making support across various fields such as urban management, regional planning, and environmental remediation, establishing geographic information as a vital component of the information era. The introduction of the “Digital Earth” concept has further accelerated the advancement of GIS, which serves as its technical foundation. Concurrently, scholars have been dedicated to theoretical research in areas like spatial cognition, spatial data uncertainty, and the formalization of spatial relationships. This reflects the dual nature of GIS as both an applied technology and an academic discipline, with the two aspects forming a mutually reinforcing cycle of progress.