堆的实现之深入分析

以前在学习堆时,写了两篇文章:数据结构--堆的实现(上)  和  数据结构--堆的实现(下),  感觉对堆的认识还是不够。本文主要分析数据结构 堆(讨论小顶堆)的基本操作的一些细节,比如 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)转换成删除堆顶元素。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/4553a8005627b5c45aae52ce73cf53b9.html