利用大根堆实现堆排序

悠悠 2023-01-21 14:17 31阅读 0赞

大根堆的结构为完全二叉树 任意一颗子树的最大值在树根上，其根节点和子节点的坐标索引关系为，i位置的节点的：[具体大根堆的介绍和实现参考另外一篇文章][Link 1]

*  左子节点索引为：2\*i+1
 *  右子节点索引坐标为：2\*i+2
 *  父节点坐标为： (i-1)/2

用大根堆实现堆排序实现的思路为，利用大根堆的特点将最后一个节点元素和0位置元素进行交换，然后将0位置元素下沉，保持大根堆结构即可完成。其中在建立大根堆时有两种方式：

*  采用由上到下的形式建立大根堆
 *  采用由下到上的方式建立大根堆

其中由下自上的形式建立的大根堆时间复杂度小，因为下部叶子节点占的数量多，而叶子节点需要移动的少。  
参考代码：

package cn.algorithms.sort.heap;
    
    import cn.algorithms.util.ArrayUtil;
    import cn.dataStructures.heap.util.HeapUtil;
    
    /** * Created with IntelliJ IDEA. * * @Description: * @Auther: TaoistQu * @Date: 2021/05/16/17:30 */
    public class HeapSort { 
        /** * 使用从上到下的形式创建大根堆 * * @param arr 要排序数组 */
        public static void heapTopSort(int[] arr) { 
            if (arr == null || arr.length < 2) { 
                return;
            }
            for (int i = 0; i < arr.length; i++) { 
                HeapUtil.heapInsert(arr, i);
            }
            int heapSize = arr.length;
            ArrayUtil.swap(arr, 0, --heapSize);
            while (heapSize > 0) { 
                HeapUtil.heapify(arr, 0, heapSize);
                ArrayUtil.swap(arr, 0, --heapSize);
            }
        }
    
        /** * 使用从下至上的形式创建堆 可以减少创建堆的时间复杂度 * * @param arr */
        public static void heapBottom(int[] arr) { 
            if (arr == null || arr.length < 2) { 
                return;
            }
            for (int i = arr.length - 1; i >= 0; i--) { 
                HeapUtil.heapify(arr, i, arr.length);
            }
            int heapSize = arr.length;
            ArrayUtil.swap(arr, 0, --heapSize);
            while (heapSize > 0) { 
                HeapUtil.heapify(arr, 0, heapSize);
                ArrayUtil.swap(arr, 0, --heapSize);
            }
        }
    }

用对数器测试结果：

package cn.algorithms.sort;
    
    import cn.algorithms.sort.heap.HeapSort;
    import cn.algorithms.util.ArrayUtil;
    
    /** * 测试各种排序算法 * * @author TaoistQu * @version 1.0 * @date 2021/1/13 23:09 */
    public class TestSort { 
        public static void main(String[] args) { 
            int testTime = 500000;
            int maxValue = 100;
            int maxSize = 100;
            boolean succeed = true;
            for (int i = 0; i < testTime; i++) { 
                int[] arr1 = ArrayUtil.generateRandomArray(maxSize, maxValue);
                int[] arr2 = ArrayUtil.copyArray(arr1);
                // BubbleSort.bubbleSort(arr1);
                // SelectionSort.selectionSort(arr1);
                //InsertionSort.insertionSort(arr1);
                //MergeSort.mergeSort1(arr1);
                //MergeSort.mergeSort2(arr1);
                // UnRecursiveQuickSort.quickSort(arr1);
                // HeapSort.heapBottom(arr1);
                HeapSort.heapTopSort(arr1);
                ArrayUtil.comparator(arr2);
                if (!ArrayUtil.isEqual(arr1, arr2)) { 
                    succeed = false;
                    ArrayUtil.printArray(arr1);
                    break;
                }
                if (i == testTime - 1)
                    ArrayUtil.printArray(arr1);
            }
            System.out.println(succeed ? "Nice" : "Fucking fucked!");
        }
    }

运行结果：  
![运行结果：][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzQ3NzM1_size_16_color_FFFFFF_t_70_pic_center]  
[具体代码github地址][github]

[Link 1]: https://blog.csdn.net/qq_36747735/article/details/116897093?spm=1001.2014.3001.5502
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzQ3NzM1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221020/2bcb703523864f79b16d191fce2620c5.png
[github]: https://github.com/TaoistQu/Algorithms/blob/master/src/main/java/cn/algorithms/sort/heap/HeapSort.java