数据结构: 堆的相关操作
写在前面:
这几天花了一些时间将“数据结构—堆”的相关操作和逻辑原理捋了捋。今天简明扼要的做一下小结。
在正式看“堆”之前,大家先读一下我在百度截取的关于堆的定义。
那么,我截取这句话的目的就在于大家重点理解最后一句: 堆通常可以被看做一棵树的数组对象。
这里提一下二叉树的顺序存储:
二叉树的顺序存储,就是用一组连续的存储单元存放二叉树中的结点。因此,必须把二叉树的所有结点安排成为一个恰当的序列,结点在这个序列中的相互位置能反映出结点之间的逻辑关系,用编号的方法从树根起,自上层至下层,每层自左至右地给所有结点编号,缺点是有可能对存储空间造成极大的浪费,在最坏的情况下,一个深度为k且只有k个结点的右单支树需要2k-1个结点存储空间。依据二叉树的性质,完全二叉树和满二叉树采用顺序存储比较合适,树中结点的序号可以唯一地反映出结点之间的逻辑关系,这样既能够最大可能地节省存储空间,又可以利用数组元素的下标值确定结点在二叉树中的位置,以及结点之间的关系。
图5-5(a)是一棵完全二叉树,图5-5(b)给出的图5-5(a)所示的完全二叉树的顺序存储结构。
typedef struct heap{
int *array;
int size;
int capacity;
}heap;
其实本质上就是一个动态顺序表,后边的代码实现以小堆为例,暂时不会考虑扩容问题。
最大堆和最小堆是二叉堆的两种形式。
最大堆:根结点的键值是所有堆结点键值中最大者,且每个结点的值都比其孩子的值大。
最小堆:根结点的键值是所有堆结点键值中最小者,且每个结点的值都比其孩子的值小。
最小堆和最大堆的增删改相似,其实就是把算法中的大于改为小于,把小于改为大于。堆这里,最主要的两个操作就是 :数据的下沉和上浮。下面我们来分别介绍。
下沉:
涉及操作:堆的创建,堆中元素的删除
1.堆的创建
我们可以这么想象去建立一个堆。从最后一个非叶子节点index开始,去向下调整以该节点为root的这颗小树。调整完后,index–,再去调整下一棵小树,一直到index=0,也就是调整到了数组的首元素也就是根节点为止为止。
void creatheap(heap* p, int* a, int n)
{
int i = 0;
p->array = (int*)malloc(sizeof(int)*n);
//暂时不考虑扩容
p->size = p->capacity = n;
for (; i < n; ++i)
{
p->array[i] = a[i];
}
for (i = (n - 2)/2; i >= 0;i--){
adjust_down(p->array,n,i);
}
}
2.元素的删除
注意,我们只能删除堆顶元素。所以我们删除的步骤是:
1.将堆中最后一个元素赋值给第一个元素,heap->arr[0]=heap->arr[size-1];
2.heap->size- -;
3.从root开始向下调整;
//删除元素(只能删除堆顶元素)
void HeapPop(Heap* heap)
{
//堆的删除元素算法思想:将最后一个元素覆盖原堆顶元素,再从array[0]进行调整
assert(heap->size > 0) ;
heap->array[0] = heap->array[heap->size - 1] ;
heap->size-- ;
AdjustDown(heap->array, heap->size, 0) ;
}
//向下调整
void AdjustDown(int array[], int size, int root)
{
int tmp = 0 ; //临时变量
while(1)
{
int left = 2 * root + 1 ;
int right = 2 * root + 2 ;
int min = 0 ;
//若没有左右孩子,直接返回
if(left >= size)
{
//越界
return ;
}
//如果存在右孩子(必有左孩子),则找值最小的孩子
if(right<size && array[right]<array[left])
{
min = right ;
}
else
{
min = left ;
}
//找到最小值后,再判断它与根节点的值
if(array[root] <= array[min])
{
return ;
}
else
{
tmp = array[root] ;
array[root] = array[min] ;
array[min] = tmp ;
root = min ;
}
}
}
上浮
涉及操作:元素的添加
//增加元素
void HeapInsert(Heap* heap, int val)
{
heap->array[heap->size] = val ;
heap->size++ ;
AdjustUp(heap->array, heap->size, heap->size - 1) ; //size-1就是 child
}
这个流程其实也容易想象。我们现在需要给建好的小堆中添加一个数据,如果说这个数据比他的parent节点还要小,那么就得数据交换,新数据就需要上浮。然后继续向上判断,直到parent=0(根节点)时为止。
//向上调整
void AdjustUp(int array[], int size, int child)
{
int parent = 0 ; //节点的双亲
int tmp = 0 ; //临时变量
while(child != 0)
{
parent = (child - 1 ) / 2 ;
if(array[child] > array[parent])
{
return ;
}
else
{
tmp = array[child] ;
array[child] = array[parent] ;
array[parent] = tmp ;
child = parent ;
}
}
}
这里给出完整代码:
#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
typedef int HPDataType ;
typedef struct Heap
{
HPDataType* array ;
int size ;
int capcity ;
}Heap ;
//向下调整
void AdjustDown(int array[], int size, int root)
{
int tmp = 0 ; //临时变量
while(1)
{
int left = 2 * root + 1 ;
int right = 2 * root + 2 ;
int min = 0 ;
//若没有左右孩子,直接返回
if(left >= size)
{
//越界
return ;
}
//如果存在右孩子(必有左孩子),则找值最小的孩子
if(right<size && array[right]<array[left])
{
min = right ;
}
else
{
min = left ;
}
//找到最小值后,再判断它与根节点的值
if(array[root] <= array[min])
{
return ;
}
else
{
tmp = array[root] ;
array[root] = array[min] ;
array[min] = tmp ;
root = min ;
}
}
}
//向上调整
void AdjustUp(int array[], int size, int child)
{
int parent = 0 ; //节点的双亲
int tmp = 0 ; //临时变量
while(child != 0)
{
parent = (child - 1 ) / 2 ;
if(array[child] > array[parent])
{
return ;
}
else
{
tmp = array[child] ;
array[child] = array[parent] ;
array[parent] = tmp ;
child = parent ;
}
}
}
//建堆,本例子建小堆
void CreatHeap(int array[], int size)
{
//从最后一个非叶子节点开始,一直调整到array[0]结束,
//最后一个非叶子节点为最后一个节点的双亲节点
int i = 0 ;
for(i=(size-2)/2; i>=0; i--)
{
AdjustDown(array,size,i) ;
}
}
void HeapCreatHeap(Heap* heap, int array[], int size)
{
int i = 0 ;
heap->capcity = size * 2 ;
heap->size = size ;
heap->array = (int *) malloc (sizeof(int) * size) ;
for(i=0; i<size; i++)
{
heap->array[i] = array[i] ;
}
CreatHeap(heap->array, heap->size ) ;
}
//增加元素
void HeapInsert(Heap* heap, int val)
{
heap->array[heap->size] = val ;
heap->size++ ;
AdjustUp(heap->array, heap->size, heap->size - 1) ; //size-1就是 child
}
//删除元素(只能删除堆顶元素)
void HeapPop(Heap* heap)
{
//堆的删除元素算法思想:将最后一个元素覆盖原堆顶元素,再从array[0]进行调整
assert(heap->size > 0) ;
heap->array[0] = heap->array[heap->size - 1] ;
heap->size-- ;
AdjustDown(heap->array, heap->size, 0) ;
}
//返回堆顶元素值
HPDataType HeapTop(Heap* heap)
{
assert(heap->size > 0) ;
return heap->array[0] ;
}
//打印
void HeapPrint(Heap* heap, int size)
{
int i = 0 ;
for(i=0; i<heap->size; i++)
{
printf("%d ", heap->array[i]) ;
}
printf("\n") ;
}
欢迎大家评论区指正。