堆排序模板

淩亂°似流年 2022-10-06 08:52 110阅读 0赞

public class Main { 
    
        public static void main(String[] args) { 
            int[] arr = { 1, 3, 5, 7, 9, 11};
            headSort(arr, arr.length);
            for (int i = 0; i < arr.length; i++) { 
                System.out.println(arr[i]);
            }
        }
    
        public static void headSort(int[] tree, int n) { 
            buildHeap(tree, n);
            for (int i = n - 1; i >= 0; i--) { 
                swap(tree, i, 0);
                heapfiy(tree, 0, i);
            }
        }
    
        public static void buildHeap(int[] tree, int n) { 
            int parentIndex = (n - 1) >> 1;
            for (int i = parentIndex; i >= 0; i--) { 
                heapfiy(tree, i, n);
            }
        }
    
        public static void heapfiy(int[] tree, int index, int n) { 
            if (index >= n) { 
                return;
            }
            int leftChildIndex = (index << 1) + 1;
            int rightChildIndex = (index << 1) + 2;
            int maxIndex = index;
            if (leftChildIndex < n && tree[maxIndex] < tree[leftChildIndex]) { 
                maxIndex = leftChildIndex;
            }
            if (rightChildIndex < n && tree[maxIndex] < tree[rightChildIndex]) { 
                maxIndex = rightChildIndex;
            }
            if (maxIndex != index) { 
                swap(tree, index, maxIndex);
                heapfiy(tree, maxIndex, n);
            }
        }
    
        public static void swap(int[] tree, int aIndex, int bIndex) { 
            int temp = tree[aIndex];
            tree[aIndex] = tree[bIndex];
            tree[bIndex] = temp;
        }
    
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，110人围观）

还没有评论，来说两句吧...

相关阅读

相关 ①归并排序、快速排序、堆排序、计数排序[算法、代码模板、面试题]

归并排序是一种分治法（Divide and Conquer）的经典排序算法，它的基本思想是将原始数组划分成较小的数组，然后递归地对这些小数组进行排序，最后再将排好序的小数...

心已赠人/ 2024年04月17日 10:18/ 0 赞/ 77 阅读

相关堆排序模板

public class Main { public static void main(String[] args) {

淩亂°似流年/ 2022年10月06日 08:52/ 0 赞/ 111 阅读

相关排序-堆排序

1.堆排序前言前面博客中讲到简单选择排序，它在待排序的n个记录中选择一个最小的记录需要比较n-1次。本来这也可以理解，查找第一个数据需要比较这么多次是正常的，否则如何知

旧城等待，/ 2022年09月30日 06:45/ 0 赞/ 243 阅读

相关 C++模板堆排序

堆排序简介堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小

爱被打了一巴掌/ 2022年07月28日 01:03/ 0 赞/ 125 阅读

相关【排序】堆排序

堆的定义设有n个元素的序列 k1，k2，…，kn，当且仅当满足下述关系之一时，称之为堆。 ![图示][SouthEast] 解释：如果让满足以上条件的元素序列（k

分手后的思念是犯贱/ 2022年06月18日 11:47/ 0 赞/ 281 阅读

相关排序——堆排序

堆排序代码 include <iostream> using namespace std; include <stdio.h> in

墨蓝/ 2022年05月21日 12:05/ 0 赞/ 272 阅读

相关堆模板

小根堆越小的整数优先级越大 include<iostream> include<cstdio> include<algorithm> inc

悠悠/ 2022年05月16日 06:48/ 0 赞/ 102 阅读

相关堆模板

include<bits/stdc++.h> using namespace std; int tail=1,a[100]; void inse

梦里梦外;/ 2022年03月20日 04:18/ 0 赞/ 126 阅读

相关堆和堆排序

堆排序堆排序基本介绍 1. 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 O(nlogn)，它也

柔光的暖阳◎/ 2021年10月19日 21:12/ 0 赞/ 414 阅读

相关排序-堆排序

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 在说明堆排序的过程前得先了解什么是堆：先看下图（来源

清疚/ 2021年09月20日 03:22/ 0 赞/ 452 阅读