侧边栏壁纸
博主头像
惊羽博主等级

hi ,我是惊羽,前生物学逃兵,现系统工程沉迷者 . 贝壳签约工程师 , 曾被雇佣为 联拓数科 · 支付研发工程师 、京东 · 京东数科 · 研发工程师、中国移动 · 雄安产业研究院 · 业务中台技术负责人 .

  • 累计撰写 101 篇文章
  • 累计创建 14 个标签
  • 累计收到 14 条评论

算法练习(21) - 大顶堆

惊羽
2022-03-08 / 0 评论 / 0 点赞 / 78 阅读 / 355 字
温馨提示:
本文为原创作品,感谢您喜欢~

0. questtion

Build the sequence of integers using the maximum heap sort method

1. background knowledge

$\sum_{0}^{h}*(h/2^{h})=2$

2 resolution

2.1 the principle

Use recursion to make each node conform to the characteristics of the heap

2.2 the code

public class BuildHeapTest{

    @Test
    public void buildHeap_test() {
        int[]  arr = {1,2,3,4,7,8,9,10,14,16};
        buildHeap(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    private void buildHeap(int[] arr) {
        for (int i = arr.length; i >= 0; i--) {
            maxHeap(arr,i);
        }
    }

    private void maxHeap(int[] arr, int i) {
        int leftI = 2*(i+1) - 1;
        int rightI = 2*(i+1);
        // 没有子节点
        if(arr.length -1 < leftI && arr.length -1 < rightI){
            return;
        }
        // 只有左子节点
        if(arr.length -1 >= leftI && arr.length -1 < rightI){
            // 调整arr[i] 与 arr[leftI] 的位置
            if(arr[leftI] >= arr[i]){
                int temp = arr[leftI];
                arr[leftI] = arr[i];
                arr[i] = temp;
                maxHeap(arr,leftI);
            }
        }
        // 左右子节点都有
        else{
            // 调整arr[i] 与 arr[leftI] 的位置
            if(arr[leftI] >= arr[i] && arr[leftI] >= arr[rightI]){
                int temp = arr[leftI];
                arr[leftI] = arr[i];
                arr[i] = temp;
                maxHeap(arr,leftI);
            }
            // 调整arr[i] 与 arr[rightI] 的位置
            if(arr[rightI] >= arr[i] && arr[rightI] >= arr[leftI]){
                int temp = arr[rightI];
                arr[rightI] = arr[i];
                arr[i] = temp;
                maxHeap(arr,rightI);
            }
        }

    }
}

3 Complexity analysis

if $h$ is the height of the heap tree,the complexity of build max-heap is :
cause a tree with $n$ nodes, height $h$ , it can most has $(n/2^{h+1})$ nodes,then $$O(f(n))=\sum_{0}^{h}*(n/2^{h+1})*O(h)=O(\sum_{0}^{h}*(n/2^{h+1})*h)=O(n*\sum_{0}^{h}*(h/2^{h+1}))$$ cause $\sum_{0}^{h}*(h/2^{h+1})=2$ , then $$O(n*\sum_{0}^{h}*(h/2^{h+1}))=O(n)$$
0
广告 广告

评论区