数据结构--堆的实现之深入分析

简介:

一,介绍

以前在学习堆时,写了两篇文章:数据结构--堆的实现(上)   和   数据结构--堆的实现(下),  感觉对堆的认识还是不够。本文主要分析数据结构 堆(讨论小顶堆)的基本操作的一些细节,比如 insert(插入)操作 和 deleteMin(删除堆顶元素)操作的实现细节、分析建堆的时间复杂度、堆的优缺点及二叉堆的不足。

 

二,堆的实现分析

堆的物理存储结构是一维数组,逻辑存储结构是完全二叉树。堆的基本操作有:insert--向堆中插入一个元素;deleteMin--删除堆顶元素

故堆的类架构如下:

复制代码
public class BinaryHeap<T extends Comparable<? super T>> {
    
    private T[] array;
    private int currentSize;
    
    public BinaryHeap() {
        
    }
    
    public BinaryHeap(T[] array){
        
    }
    
    public void insert(T x){
        //do something
    }
    public T deleteMin(){
        
    }
    
    //other operations....
}
复制代码

 

①insert操作

复制代码
1     public void insert(T x){
2         if(currentSize == array.length - 1)//数组0号位置作为哨兵
3             enlarge(array.length * 2 + 1);0
4         
5         int hole = currentSize++;
6         for(array[0] = x; x.compareTo(array[hole / 2]) < 0; hole /= 2)
7             array[hole] = array[hole / 2];//将父节点往下移
8         array[hole] = x;//将待插入的元素放置到合适位置
9     }
复制代码

1)数组0号元素作为哨兵,可以避免交换操作。

因为,在与父节点的比较过程中,若父节点比待插入的节点大(子节点),则需要交换父节点和待插入节点。而引入哨兵,将待插入节点保存在数组0号元素处,当父节点比待插入的节点大时,直接用父节点替换待插入的节点大(子节点)。

2)复杂度分析

可以看出,最坏情况下,比较进行到根节点时会结束。因此,insert操作时间取决于树的高度。故复杂度为O(logN)。但是在平均情况下,insert操作只需要O(1)时间就能完成,因为毕竟并不是所有的节点都会被调度至根结点,只有在待插入的节点的权值最小时才会向上调整堆顶。

此外,对于二叉树,求解父节点操作: hole = hole / 2, 除以2可以使用右移一位来实现。

因此,可以看出d叉树(完成二叉树 d=2 ),当 d 很大时,树的高度就很小,插入的性能会有一定的提高。为什么说是一定的??后面会详细分析。

 

②deleteMin操作

deleteMin操作将堆中最后一个元素替换第一个元素,然后在第一个元素处向下进行堆调整。

复制代码
 1     public AnyType deleteMin( )
 2     {
 3         if( isEmpty( ) )
 4             throw new UnderflowException( );
 5 
 6         AnyType minItem = findMin( );
 7         array[ 1 ] = array[ currentSize-- ];//最后一个元素替换堆顶元素
 8         percolateDown( 1 );//向下执行堆调整
 9 
10         return minItem;
11     }
复制代码

 

复制代码
 1     /**
 2      * Internal method to percolate down in the heap.
 3      * @param hole the index at which the percolate begins.
 4      */
 5     private void percolateDown( int hole )
 6     {
 7         int child;
 8         AnyType tmp = array[ hole ];
 9 
10         for( ; hole * 2 <= currentSize; hole = child )
11         {
12             child = hole * 2;
13             if( child != currentSize &&
14                     array[ child + 1 ].compareTo( array[ child ] ) < 0 )
15                 child++;
16             if( array[ child ].compareTo( tmp ) < 0 )
17                 array[ hole ] = array[ child ];
18             else
19                 break;
20         }
21         array[ hole ] = tmp;
22     }
复制代码

当从第一个元素(堆顶元素)处向下进行堆调整时,一般该元素会被调整至叶子结点。堆顶元素的高度为树的高度。故时间复杂度为:O(logN)。

 

③其他一些操作

1)decreaseKey(p,Δ)/increaseKey(p,Δ)---更改位置p处元素的权值

这两个操作一般不常用。它们会破坏堆的性质。因此,当修改了p处元素的权值时,需要进行堆调整(decreseKey为向上调整,increaseKey为向下调整)

2)delete(p)--删除堆中位置为p处的元素

前面介绍的deleteMin操作删除的是堆顶元素,那如何删除堆中的任一 一个元素?

其实,可以将删除堆中任一 一个元素(该元素位置为 p)转换成删除堆顶元素。

借助 1)中的修改位置p处元素的权值操作:decrese(p,Δ)。将p处元素的权值降为负无穷大。此时,该元素会向上调整至堆顶,然后执行deleteMin即可。

 

三,建堆(buildHeap)

从最后一个非叶子结点开始向前进行向下调整。

复制代码
1     /**
2      * Establish heap order property from an arbitrary
3      * arrangement of items. Runs in linear time.
4      */
5     private void buildHeap( )
6     {
7         for( int i = currentSize / 2; i > 0; i-- )
8             percolateDown( i );
9     }
复制代码

i 的初始值为最后一个非叶子结点的位置。

 时间复杂度分析:

建堆的时间复杂度与堆中所有的结点的高度相同。

 分析如下:首先,叶子结点的高度为0。而建堆,就是从最后一个非叶子结点开始,不断调用percolateDown(i),percolateDown(i)方法的时间复杂度就是位置 i 处节点的高度。在上面第7行for循环中,当 i 自减为1时,表明已经到了堆顶元素,因此整个buildHeap的时间复杂度就是所有非叶子结点的高度之和。而叶子结点的高度为0,故buildHeap的时间复杂度可理解成 整个二叉堆的所有的结点的高度之和。

而对于理想二叉堆而言:(二叉堆是一颗完全二叉树,理想二叉堆为满二叉树)

所有结点的高度之为:2^(h+1)-1-(h+1)。其中,h表示二叉堆的高度

又可以表示成:N-b(N),N是堆中结点的个数,b(N)是N的二进制表示法中1的个数,如:b(7)=3

 

四,d 堆

上面分析了二叉堆的基本操作。那什么是 d 堆呢?为什么要有 d 堆呢?

对于二叉堆,d=2。顾名思义,d堆就是所有节点都有d个儿子的堆。为什么需要这种堆?

分析二叉堆的基本操作,insert操作需要定位父结点,这需要一个除法操作,操作的次数与树的高度有关。deleteMin操作需要找出所有儿子中权值最小的那个儿子,而寻找儿子节点则需要乘法操作,操作的复杂度与儿子的个数有关(d越大,节点的儿子数越多,查找越慢)。

假设,我们的需求是有大量的insert操作,而仅有少量的deleteMin,那d堆从理论上讲就有性能优势了。因为d 远大于2时,树的高度很小啊,但是当d不是2的倍数时,除法操作不能通过移位来实现,也许会有一定的性能损失,这也是为什么insert操作分析中讲的“插入性能会有一定的提高”。

而如果有大量的deleteMin操作,那d堆反而可能会除低性能,因为:d 越大,说明节点的儿子个数越多,找出权值最小的儿子就需要更多的比较次数了。

可见,d堆的提出,是因为需求不同而导致的。比如,insert属于高频需求.....

 

五,二叉堆的不足

根据上面的分析,二叉堆的insert复杂度O(logN),deleteMin最坏也是O(logN)。

但是如果需要查找堆中某个元素呢?或者需要合并两个堆呢?

对于二叉堆而言,对find 和 merge操作的支持不够。这是由二叉堆的存储结构决定的,因为二叉堆中的元素实际存储在数组中。正因为如此,所有支持有效合并的高级数据结构都需要使用链式数据结构。另外,关于数据结构的合并操作,可参考:数据结构--并查集的原理及实现

 

六,其他形式的“堆”

为了克服二叉堆的不足,提出了一面一些类型的堆,它们主要是为了支持merge 和 find 操作。这就不详细介绍了。

①左式堆

对堆的结构有一定的要求:它有一个“零路径长”的概念,①任意一个节点的零路径长比它的各个儿子的零路径长的最小值大1。②对于堆中每一个节点,它的左儿子的零路径长至少与右儿子的零路径长相等。

 

②斜堆

对堆的结构没有要求。

 

③二项队列

 最大的特点就是,做到了merge操作时间复杂度为O(logN),而insert操作的平均时间复杂度为O(1)。

关于二项队列,可参考:数据结构--二项队列分析及实现

 

参考的BinaryHeap的完整实现如下:

复制代码
package c9.shortestPath;
// BinaryHeap class
//
// CONSTRUCTION: with optional capacity (that defaults to 100)
//               or an array containing initial items
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// Comparable deleteMin( )--> Return and remove smallest item
// Comparable findMin( )  --> Return smallest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// ******************ERRORS********************************
// Throws RuntimeExceptionException as appropriate

/**
 * Implements a binary heap.
 * Note that all "matching" is based on the compareTo method.
 * @author Mark Allen Weiss
 */
public class BinaryHeap<AnyType extends Comparable<? super AnyType>>
{
    /**
     * Construct the binary heap.
     */
    public BinaryHeap( )
    {
        this( DEFAULT_CAPACITY );
    }

    /**
     * Construct the binary heap.
     * @param capacity the capacity of the binary heap.
     */
    public BinaryHeap( int capacity )
    {
        currentSize = 0;
        array = (AnyType[]) new Comparable[ capacity + 1 ];
    }
    
    /**
     * Construct the binary heap given an array of items.
     */
    public BinaryHeap( AnyType [ ] items )
    {
            currentSize = items.length;
            array = (AnyType[]) new Comparable[ ( currentSize + 2 ) * 11 / 10 ];

            int i = 1;
            for( AnyType item : items )
                array[ i++ ] = item;
            buildHeap( );
    }

    /**
     * Insert into the priority queue, maintaining heap order.
     * Duplicates are allowed.
     * @param x the item to insert.
     */
    public void insert( AnyType x )
    {
        if( currentSize == array.length - 1 )
            enlargeArray( array.length * 2 + 1 );

            // Percolate up
        int hole = ++currentSize;
        for( array[ 0 ] = x; x.compareTo( array[ hole / 2 ] ) < 0; hole /= 2 )
            array[ hole ] = array[ hole / 2 ];
        array[ hole ] = x;
    }


    private void enlargeArray( int newSize )
    {
            AnyType [] old = array;
            array = (AnyType []) new Comparable[ newSize ];
            for( int i = 0; i < old.length; i++ )
                array[ i ] = old[ i ];        
    }
    
    /**
     * Find the smallest item in the priority queue.
     * @return the smallest item, or throw an UnderflowException if empty.
     */
    public AnyType findMin( )
    {
        if( isEmpty( ) )
            throw new RuntimeException( );
        return array[ 1 ];
    }

    /**
     * Remove the smallest item from the priority queue.
     * @return the smallest item, or throw an UnderflowException if empty.
     */
    public AnyType deleteMin( )
    {
        if( isEmpty( ) )
            throw new RuntimeException( );

        AnyType minItem = findMin( );
        array[ 1 ] = array[ currentSize-- ];
        percolateDown( 1 );

        return minItem;
    }

    /**
     * Establish heap order property from an arbitrary
     * arrangement of items. Runs in linear time.
     */
    public void buildHeap( )
    {
        for( int i = currentSize / 2; i > 0; i-- )
            percolateDown( i );
    }

    /**
     * Test if the priority queue is logically empty.
     * @return true if empty, false otherwise.
     */
    public boolean isEmpty( )
    {
        return currentSize == 0;
    }

    /**
     * Make the priority queue logically empty.
     */
    public void makeEmpty( )
    {
        currentSize = 0;
    }

    private static final int DEFAULT_CAPACITY = 10;

    private int currentSize;      // Number of elements in heap
    private AnyType [ ] array; // The heap array

    /**
     * Internal method to percolate down in the heap.
     * @param hole the index at which the percolate begins.
     */
    private void percolateDown( int hole )
    {
        int child;
        AnyType tmp = array[ hole ];

        for( ; hole * 2 <= currentSize; hole = child )
        {
            child = hole * 2;
            if( child != currentSize &&
                    array[ child + 1 ].compareTo( array[ child ] ) < 0 )
                child++;
            if( array[ child ].compareTo( tmp ) < 0 )
                array[ hole ] = array[ child ];
            else
                break;
        }
        array[ hole ] = tmp;
    }

        // Test program
    public static void main( String [ ] args )
    {
        int numItems = 10000;
        BinaryHeap<Integer> h = new BinaryHeap<>( );
        int i = 37;

        for( i = 37; i != 0; i = ( i + 37 ) % numItems )
            h.insert( i );
        for( i = 1; i < numItems; i++ )
            if( h.deleteMin( ) != i )
                System.out.println( "Oops! " + i );
    }
}
复制代码

 

参考资料

数据结构与算法分析 Mark Allen Weiss著
本文转自hapjin博客园博客,原文链接:http://www.cnblogs.com/hapjin/p/5459991.html,如需转载请自行联系原作者

相关文章
|
3月前
|
算法 安全 大数据
揭秘!Python堆与优先队列:数据结构的秘密武器,让你的代码秒变高效战士!
【7月更文挑战第8天】Python的heapq模块和queue.PriorityQueue提供堆与优先队列功能,助你提升算法效率。堆用于快速找大数据集的第K大元素,如示例所示,时间复杂度O(n log k)。PriorityQueue在多线程中智能调度任务,如模拟下载管理器,按优先级处理任务。掌握这些工具,让代码运行更高效!
60 1
|
18天前
|
存储 Java
【数据结构】优先级队列(堆)从实现到应用详解
本文介绍了优先级队列的概念及其底层数据结构——堆。优先级队列根据元素的优先级而非插入顺序进行出队操作。JDK1.8中的`PriorityQueue`使用堆实现,堆分为大根堆和小根堆。大根堆中每个节点的值都不小于其子节点的值,小根堆则相反。文章详细讲解了如何通过数组模拟实现堆,并提供了创建、插入、删除以及获取堆顶元素的具体步骤。此外,还介绍了堆排序及解决Top K问题的应用,并展示了Java中`PriorityQueue`的基本用法和注意事项。
23 5
【数据结构】优先级队列(堆)从实现到应用详解
|
2月前
|
存储 算法
【数据结构】堆
【数据结构】堆
|
2月前
|
搜索推荐 算法 Go
深入探索堆:Go语言中的高效数据结构
深入探索堆:Go语言中的高效数据结构
|
2月前
|
存储 算法 Linux
【数据结构】树、二叉树与堆(长期维护)(1)
【数据结构】树、二叉树与堆(长期维护)(1)
|
2月前
|
算法
【数据结构】树、二叉树与堆(长期维护)(2)
【数据结构】树、二叉树与堆(长期维护)(2)
【数据结构】树、二叉树与堆(长期维护)(2)
|
3月前
|
存储 算法
【数据结构】堆,堆的实现,堆排序,TOP-K问题
数据结构——堆,堆的实现,堆排序,TOP-K问题
38 1
【数据结构】堆,堆的实现,堆排序,TOP-K问题
|
2月前
【数据结构】二叉树顺序实现(大堆)-->赋源码
【数据结构】二叉树顺序实现(大堆)-->赋源码
34 4
|
1月前
|
存储 程序员 C语言
堆和栈之间有什么区别
【9月更文挑战第1天】堆和栈之间有什么区别
117 0
|
2月前
|
算法 机器人
【数据结构】什么是堆
【数据结构】什么是堆
36 0