算法系列--堆

262 阅读2分钟

0.引言

堆是一种比较常见的数据结构,堆排序也是面试时会经常遇到的问题,今天就分析一下堆。

1.堆结构

堆是一种类似于树的数据结构,父节点和子节点之间存在一定的关系,子节点的数量根据堆的类型来决定,最长见得就是每个父节点最多两个子节点的二叉堆。

如图所示,我们用一个数组类模拟二叉树以构建二叉堆,从图可以看出,堆是从数组的1开始而不是0开始,这主要就是为了构建子节点和父节点的关系,我们可以很清楚的看到这种关系:leftNodeIndex=rootIndex2; rightNodeIndex=rootIndex2+1。 我们还可以发现这个堆的父节点都是大于其子节点的,这就是一个最大堆,可以用来进行从小到大的堆排序。

2.构建最大堆

构建最大堆,首先明确一个规则,堆的叶子节点的位置,假设堆的数量为N=7; 那么它的叶子节点就是 N/2+1,N/2+2,N/2+3,N/2+4,如图所示:

那么现在假设给了一个堆数组,构建成一个最大堆,从叶子节点的上一层节点开始直到根节点进行最大堆化操作

void build_maxheap (int Arr[ ])
{
    for(int i = N/2 ; i >= 1 ; i-- )
    {
        max_heapify (Arr, i) ;
    }
}


void max_heapify (int Arr[ ], int i, int N)
{
    int left = 2*i                   //left child
    int right = 2*i +1           //right child
    if(left<= N and Arr[left] > Arr[i] )
          largest = left;
    else
         largest = i;
    if(right <= N and Arr[right] > Arr[largest] )
        largest = right;
    if(largest != i )
    {
        swap (Arr[i] , Arr[largest]);
        max_heapify (Arr, largest,N);
    } 
 }

max_heapify就是递归的将父节点和左右子节点进行大小比较,将较大的值放到父节点的位置。下图演示了一个构建最大堆的过程

最小堆和最大堆相反,就是根节点是小于子节点的,只要将max_heapify稍加改造就可以了,就不再赘言了。

3.堆排序

说到应用了,如果给定了一个无序的数组按照从小到大排序,那么我们就可以利用最大堆的性质在O(NlogN)的时间复杂度内进行排序。 堆排序一般按照如下步骤: 1.构建最大堆。 2.交换第一个元素和最后一个元素的位置。 3.从根节点开始,进行堆最大化操作(max_heapfy),注意此时待排序节点的个数为N-1,因为第二步的时候已经排序好一个值了。 4.重复2,3步骤直到排序完成。 如果是从大到小排序,那么就用最小堆。 排序过程入下图:

 void heap_sort(int Arr[ ])
{
    int heap_size = N;
    build_maxheap(Arr);
    for(int i = N; i>=2 ; i-- )
    {
        swap(Arr[ 1 ], Arr[ i ]);
        heap_size = heap_size-1;
        max_heapify(Arr, 1, heap_size);
    }
}

至此堆的基础知识就差不多了。

关注我的公众号: