算法与数据结构全阶班-左程云版(二)基础阶段之4.堆和比较器(中)

简介: 本文主要介绍了堆和比较器:堆包括大根堆和小根堆;比较器的实质就是重载比较运算符,可以用于普通方式的排序和自定义的排序。

现在进一步实现堆排序

package heap04;
/**
 * @author Corley
 * @date 2021/10/12 20:16
 * @description LeetCodeAlgorithmZuo-heap04
 */
public class HeapSort {
    /*
        新加进来的数,现在停在了index位置,请依次往上移动
         */
    private void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
        }
    }
    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    /*
    从index位置,往下看,不断的下沉
    停:较大的子节点都不再比index位置的数大;已经没子节点
     */
    public void heapify(int[] arr, int index, int heapSize) {
        int left = 2 * index + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && arr[left] < arr[left + 1] ? left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = 2 * index + 1;
        }
    }
    /*
     * 堆排序
     * */
    public void heapSort(int[] arr) {
        if (null == arr || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        while (heapSize > 0) {
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }
}

现在分析时间复杂度

建堆时,调用heapInsert(arr, i)方法N次,时间复杂度为O(N*LogN),while循环也是O(N*LogN),整体时间复杂度也是O(N*LogN)

如果只是将数组变成大根堆,而不一定数组有序,可以优化为O(N)的时间复杂度,如下:

2345_image_file_copy_139.jpg

实现如下:

public void heapSort(int[] arr) {
    if (null == arr || arr.length < 2) {
        return;
    }
    /*for (int i = 0; i < arr.length; i++) {
        heapInsert(arr, i);
    }*/
    for (int i = arr.length - 1; i >= 0; i--) {
        heapify(arr, i, arr.length);
    }
    int heapSize = arr.length;
    swap(arr, 0, --heapSize);
    while (heapSize > 0) {
        heapify(arr, 0, heapSize);
        swap(arr, 0, --heapSize);
    }
}

现在进行证明,时间复杂度为O(N)

2345_image_file_copy_140.jpg

2345_image_file_copy_141.jpg

堆排序的优势:

堆排序实现了O(N*LogN)的时间复杂度,但是只使用了有限的几个变量,达到了空间复杂度O(1)。

综上,堆排序:

1,先让整个数组都变成大根堆结构,建立堆的过程:

1)从上到下的方法heapinsert,时间复杂度为O(N*logN);

2)从下到上的方法heapify,时间复杂度为O(N)。

直观说明如下:

2345_image_file_copy_143.jpg

2,把堆的最大值和堆末尾的值交换,然后减少堆的大小之后,再去调整堆。一直周而复始,时间复杂度为O(N*logN)

3,堆的大小减小成0之后,排序完成

现在实现使用系统的堆:

package heap04;
import java.util.PriorityQueue;
/**
 * @author Corley
 * @date 2021/10/13 14:56
 * @description LeetCodeAlgorithmZuo-heap04
 */
public class HeapUse {
    public static void main(String[] args) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        heap.add(5);
        heap.add(7);
        heap.add(3);
        heap.add(0);
        heap.add(5);
        heap.add(2);
        while (!heap.isEmpty()) {
            System.out.println(heap.poll());
        }
    }
}

优先队列的底层就是堆,默认是小根堆。

与堆有关的题目:

已知一个几乎有序的数组。几乎有序是指,如果把数组排好顺序的话,每个元素移动的距离一定不超过k,并且k相对于数组长度来说是比较小的。

请选择一个合适的排序策略,对这个数组进行排序。

分析:

方式是准备一个k+1大小的堆,放入

2345_image_file_copy_145.jpg

实现如下:

package heap04;
import java.util.PriorityQueue;
/**
 * @author Corley
 * @date 2021/10/13 15:12
 * @description LeetCodeAlgorithmZuo-heap04
 */
public class SortArrayDistanceLessK {
    public static void SortedArrayDistanceLessK(int[] arr, int k) {
        if (0 == k) {
            return;
        }
        // 小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int index = 0;
        for (; index <= k; index++) {
            heap.add(arr[index]);
        }
        int i = 0;
        for (; index < arr.length; i++, index++) {
            arr[i] = heap.poll();
            heap.add(arr[index]);
        }
        while (!heap.isEmpty()) {
            arr[i++] = heap.poll();
        }
    }
}

复杂度为:O(N*LogK)

相关文章
|
1月前
|
存储 算法 Java
散列表的数据结构以及对象在JVM堆中的存储过程
本文介绍了散列表的基本概念及其在JVM中的应用,详细讲解了散列表的结构、对象存储过程、Hashtable的扩容机制及与HashMap的区别。通过实例和图解,帮助读者理解散列表的工作原理和优化策略。
39 1
散列表的数据结构以及对象在JVM堆中的存储过程
|
16天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
27 1
|
20天前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
63 4
|
17天前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
|
17天前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
25天前
|
算法
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
86 23
|
25天前
|
算法
数据结构之蜜蜂算法
蜜蜂算法是一种受蜜蜂觅食行为启发的优化算法,通过模拟蜜蜂的群体智能来解决优化问题。本文介绍了蜜蜂算法的基本原理、数据结构设计、核心代码实现及算法优缺点。算法通过迭代更新蜜蜂位置,逐步优化适应度,最终找到问题的最优解。代码实现了单链表结构,用于管理蜜蜂节点,并通过适应度计算、节点移动等操作实现算法的核心功能。蜜蜂算法具有全局寻优能力强、参数设置简单等优点,但也存在对初始化参数敏感、计算复杂度高等缺点。
57 20
|
16天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
43 1
|
1月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
71 16
|
25天前
|
机器学习/深度学习 算法 C++
数据结构之鲸鱼算法
鲸鱼算法(Whale Optimization Algorithm,WOA)是由伊朗研究员Seyedali Mirjalili于2016年提出的一种基于群体智能的全局优化算法,灵感源自鲸鱼捕食时的群体协作行为。该算法通过模拟鲸鱼的围捕猎物和喷出气泡网的行为,结合全局搜索和局部搜索策略,有效解决了复杂问题的优化需求。其应用广泛,涵盖函数优化、机器学习、图像处理等领域。鲸鱼算法以其简单直观的特点,成为初学者友好型的优化工具,但同时也存在参数敏感、可能陷入局部最优等问题。提供的C++代码示例展示了算法的基本实现和运行过程。
44 0

热门文章

最新文章