堆的创建、优先队列、topk、堆排序C语言实现

 

1、堆的定义

堆就是用数组实现的二叉树,所有它没有使用父指针或者子指针。

堆就是利用完全二叉树的结构来维护的一维数组。

堆的创建、优先队列、topk、堆排序C语言实现

 

 

 

创建一个堆除了一个简单的一维数组以外,不需要任何额外的空间。

如果我们不允许使用指针,那么我们怎么知道哪一个节点是父节点,哪一个节点是它的子节点呢?节点在数组中的位置index 和它的父节点已经子节点的索引之间有一个映射关系。

如果 i 是某个节点的索引,那么下面的公式就给出了它的父节点和子节点在数组中的位置:

parent(i) = floor((i - 1)/2)
left(i)   = 2i + 1
right(i)  = 2i + 2

注意 right(i) 就是简单的 left(i) + 1。左右节点总是处于相邻的位置。

 

 

2、堆的分类

按照堆的特点可以把堆分为大顶堆小顶堆

大顶堆:每个结点的值都大于等于其左右孩子结点的值,左右孩子节点无大小关系

小顶堆:每个结点的值都小于等于其左右孩子结点的值,左右孩子节点无大小关系

堆的创建、优先队列、topk、堆排序C语言实现

 

我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面这个样子

堆的创建、优先队列、topk、堆排序C语言实现

我们用简单的公式来描述一下堆的定义就是:(读者可以对照上图的数组来理解下面两个公式)

大顶堆:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 

小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] 

堆可以用来做什么

  • 构建优先队列
  • topk
  • 支持堆排序

 

3、堆和普通树的区别

堆并不能取代二叉搜索树,它们之间有相似之处也有一些不同。我们来看一下两者的主要差别:

节点的顺序:在二叉搜索树中,左子节点必须比父节点小,右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小,而在最小堆中,它们都必须比父节点大。

内存占用:普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配额为是我内存。堆仅仅使用一个数据来村塾数组,且不使用指针。

平衡:二叉搜索树必须是“平衡”的情况下,其大部分操作的复杂度才能达到O(log n)。你可以按任意顺序位置插入/删除数据,或者使用 AVL 树或者红黑树,但是在堆中实际上不需要整棵树都是有序的。我们只需要满足对属性即可,所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(log n) 的性能。

搜索:在二叉树中搜索会很快,但是在堆中搜索会很慢。在堆中搜索不是第一优先级,因为使用堆的目的是将最大(或者最小)的节点放在最前面,从而快速的进行相关插入、删除操作。

 

 

4、堆的操作

创建堆:创建小顶堆

1.将数组顺序添加到堆中。(此时堆还不算小顶堆)

2.调整堆为小顶堆

注意:

 1.for(j=(heap->Size-1)/2;j>=0;j--):比如我下面堆中有十个元素,Size大小也为10,第一次调整堆时,索引是从4开始的,那么它的左右节点分别是:9、10索引位置上的元素,很明显,10索引是不存在。
j的数字依次是4,3,2,1,0。
2.每次外层遍历都需要判断节点的左右节点是否存在(左节点存在,右节点自然存在,左右节点相邻,右节点索引=左节点索引+1),然后找出左右节点中的最小值,节点与此最小值交换,最后索引位置也交换,继续往下
#include<stdio.h>
#define MAX 100


typedef struct Heap  HeapNode;
struct Heap{
    int Arr[MAX] ;
    int Size ;
};

void print(HeapNode *heap){
     int i = 0;
    for(;i<heap->Size;i++){
      printf("%d ",heap->Arr[i]);  
    }
    printf("\n");  
}

//创建堆
HeapNode * create(){
    HeapNode *heap;
    heap = (HeapNode*)malloc(sizeof(HeapNode));
    heap->Size = 0;
    return heap;
}

//向堆中添加数据并调整为最小堆
void Add_and_Adjust(HeapNode * heap,int arr[],int len){
    //添加数组元素到堆,顺序添加就可以了
    int i =0;
    for(0;i<len;i++){
        heap->Arr[i] = arr[i];        
    }
    //赋值堆的成员个数:用于处理左右节点是否存在的判断
    heap->Size = i;
    //调整堆为最小堆:自下往上
    int j = 0;
    for(j=(heap->Size-1)/2;j>=0;j--){
        adjust(heap,j);
        print(heap);
    }
}
//自上往下
void adjust(HeapNode * heap,int root){
   while(1){
       int left = 2 * root + 1;
       int right = 2 * root + 2;
       //判断此节点的左右节点是否存在:如果左边的left都不存在,则右节点也不会存在,则该节点没有左右节点
       //通过索引位置判断
       if(left>=heap->Size){
           return ; 
       }
       //我们需要找到左右节点中的最小值
       //假设左节点为最小值
       int min = left;
       //如果右节点存在,且右节点的值小于左节点,则右节点为最小值
       if(right<heap->Size&&(heap->Arr[right] <  heap->Arr[left]))
           min = right;
       //如果根节点比左右节点中小的那个还小,则不用交换
       if(heap->Arr[root]<= heap->Arr[min])
           return ; 
       //如果根节点比左右节点中小的大,则交换
       int temp = heap->Arr[root];
       heap->Arr[root] = heap->Arr[min];
       heap->Arr[min] = temp;
       //交换后,继续往下遍历,根索引位置等于左右节点中值小些的索引
       root = min;
       
   }
}    

int main(void) {
    int arr[10] = {76,23,43,6,87,56,34,45,32,12}; 
    HeapNode *heap = create();
    Add_and_Adjust(heap,arr,10);
    return 0;
}

 

 

构建优先队列:利用堆的堆顶为最小值或者最大值的特性

需要掌握堆的插入操作:需要注意的是每次插到数组末尾,从末尾与父节点比较交换,交换后,继续往上比较,直至没有满足比较条件或者到达索引为1的节点。

1.每次插入一个元素放在堆的数组末尾

2.从末尾开始,与此元素的父节点比较,交换。

#include<stdio.h>
#define MAX 100


typedef struct Heap  HeapNode;
struct Heap{
    int Arr[MAX] ;
    int Size ;
};

void print(HeapNode *heap){
     int i = 0;
    for(;i<heap->Size;i++){
      printf("%d ",heap->Arr[i]);  
    }
    printf("\n");  
}

//创建堆
HeapNode * create(){
    HeapNode *heap;
    heap = (HeapNode*)malloc(sizeof(HeapNode));
    heap->Size = 0;
    return heap;
}

//向堆中添加数据并调整为最小堆
void Add_and_Adjust(HeapNode * heap,int arr[],int len){
    //添加数组元素到堆,顺序添加就可以了
    int i =0;
    for(0;i<len;i++){
        heap->Arr[i] = arr[i];        
    }
    //赋值堆的成员个数:用于处理左右节点是否存在的判断
    heap->Size = i;
    //调整堆为最小堆
    int j = 0;
    for(j=(heap->Size-1)/2;j>=0;j--){
        adjust(heap,j);
        print(heap);
    }
}
//从顶至下
void adjust(HeapNode * heap,int root){
   
   while(1){
       int left = 2 * root + 1;
       int right = 2 * root + 2;
       //判断此节点的左右节点是否存在:如果左边的left都不存在,则右节点也不会存在,则该节点没有左右节点
       //通过索引位置判断
       if(left>=heap->Size){
           return ; 
       }
       //我们需要找到左右节点中的最小值
       //假设左节点为最小值
       int min = left;
       //如果右节点存在,且右节点的值小于左节点,则右节点为最小值
       if(right<heap->Size&& (heap->Arr[right] <  heap->Arr[left]))
           min = right;
       //如果根节点比左右节点中小的那个还小,则不用交换
       if(heap->Arr[root]<= heap->Arr[min])
           return ; 
       //如果根节点比左右节点中小的大,则交换
       int temp = heap->Arr[root];
       heap->Arr[root] = heap->Arr[min];
       heap->Arr[min] = temp;
       //交换后,继续往下遍历,根索引位置等于左右节点中值小些的索引
       root = min;
       
   }
}

void insert(HeapNode * heap,int node){
    if(heap->Size>=MAX){
        return ;
    }
    heap->Arr[heap->Size] = node;
    heap->Size ++;
    int now = heap->Size-1;
    print(heap);
    while(now>=1){
        //找到父节点
        int root = (now -1)/2;
        //如果父节点小于此节点,结束
        if(heap->Arr[root]<=heap->Arr[now]){
          break ; 
        }  
        printf("%d:%d\n",heap->Arr[root],heap->Arr[now]);
        //交换
        int temp = heap->Arr[root];
        heap->Arr[root] = heap->Arr[now];
        heap->Arr[now] = temp;
        //继续往上交换
        now = root;  
    }   
}

int main(void) {
    int arr[10] = {76,23,43,6,87,56,34,45,32,12}; 
    HeapNode *heap = create();
    Add_and_Adjust(heap,arr,10);
    insert(heap,2);
    print(heap);
    return 0;
}

 

 

TOPk

很常见的面试题,利用堆很容易做出来。

找出最大的k个数,我们可以用最小堆来做,

新插入的元素与堆顶的元素比较,如果比它大,则将它赋值给堆顶元素,并向下调整堆(继续维持最小堆的状态),如果比堆顶元素小,则不做处理。

#include<stdio.h>
#define MAX 100


typedef struct Heap  HeapNode;
struct Heap{
    int Arr[MAX] ;
    int Size ;
};

void print(HeapNode *heap){
     int i = 0;
    for(;i<heap->Size;i++){
      printf("%d ",heap->Arr[i]);  
    }
    printf("\n");  
}

//创建堆
HeapNode * create(){
    HeapNode *heap;
    heap = (HeapNode*)malloc(sizeof(HeapNode));
    heap->Size = 0;
    return heap;
}

//向堆中添加数据并调整为最小堆
void Add_and_Adjust(HeapNode * heap,int arr[],int len){
    //添加数组元素到堆,顺序添加就可以了
    int i =0;
    for(0;i<len;i++){
        heap->Arr[i] = arr[i];        
    }
    //赋值堆的成员个数:用于处理左右节点是否存在的判断
    heap->Size = i;
    //调整堆为最小堆
    int j = 0;
    for(j=(heap->Size-1)/2;j>=0;j--){
        adjust(heap,j);
    }
}
//从顶至下
void adjust(HeapNode * heap,int root){
   
   while(1){
       int left = 2 * root + 1;
       int right = 2 * root + 2;
       //判断此节点的左右节点是否存在:如果左边的left都不存在,则右节点也不会存在,则该节点没有左右节点
       //通过索引位置判断
       if(left>=heap->Size){
           return ; 
       }
       //我们需要找到左右节点中的最小值
       //假设左节点为最小值
       int min = left;
       //如果右节点存在,且右节点的值小于左节点,则右节点为最小值
       if(right<heap->Size&& (heap->Arr[right] <  heap->Arr[left]))
           min = right;
       //如果根节点比左右节点中小的那个还小,则不用交换
       if(heap->Arr[root]<= heap->Arr[min])
           return ; 
       //如果根节点比左右节点中小的大,则交换
       int temp = heap->Arr[root];
       heap->Arr[root] = heap->Arr[min];
       heap->Arr[min] = temp;
       //交换后,继续往下遍历,根索引位置等于左右节点中值小些的索引
       root = min;
       
   }
}

void add(HeapNode * heap,int node){
    if(node <= heap->Arr[0] ){
        return ; 
    }
    heap->Arr[0]= node;
    adjust(heap,0);
}




int main(void) {
    int arr[10] = {76,23,43,6,87,56,34,45,32,12}; 
    HeapNode *heap = create();
    Add_and_Adjust(heap,arr,10);
    add(heap,59);
    add(heap,98);
    add(heap,349);
    add(heap,321);
    add(heap,125);
    print(heap);
    return 0;
}

 

 

上一篇:快排与TopK 问题


下一篇:topk问题(python版本)