数据结构:二叉堆(BinaryHeap)

概念
a、二叉堆是一种完全二叉树(故而可以使用数组来保存)。二叉堆有最大二叉堆(父节点值永远大于任意子节点的值)和最小二叉堆两种(父节点的值永远小鱼任意子节点的值)。
b、二叉堆父子节点之间有大小关系,兄弟节点之间没有大小顺序关系。

用数组表示为 [开始符,5,6,7,12,8,9,8,13,14,9]

1、结构

//
struct BinaryHeap
{
    int* elements;  //使用数组存储元素列表
    int capacity;  //数组的容量
    int size;   //当前的节点数
};

2、初始化

//
    BinaryHeapPointer bhp =  (struct BinaryHeap*)malloc(sizeof(struct BinaryHeap));
    bhp->capacity = ;//设置容量
    bhp->size = 0;
    bhp->elements = malloc(sizeof(int) * (capacity + 1));
    bhp->elements[0] = ;  //设置一个标识让0下表元素再后续使用中被忽略 后面统一从1开始 计算更为方便

3、父节点与子节点的顺序关系
a. 父节点 = 子节点/2 向下取整
b. 子节点 = 父节点 * 2 & 子节点 = 父节点 * 2 + 1

4、插入数据

为了保证(实例最小二叉堆)父节点永远小于子节点值,插入时需要保证插入位置只大于父节点而小于子节点。(最大二叉堆也同理) 入下图所示 在原二叉堆中插入元素“14”在末尾处比父节点小,则与父节点交换,一直至比父节点大位置。

5、删除根节点
如下图所示,删除根节点(最小节点)将会失去根节点,此时应该将左右节点值对比,将较小值上移,被上移的节点同样失去值 需要将其2个子节点继续对比将最小值上移。。。。直至没有子节点可以上移。然后将最后一个节点移动至最后空出来的节点即可。

6、代码实现

//
//
//  BinaryHeap.h
//  AVLTree
//

#ifndef BinaryHeap_h
#define BinaryHeap_h

#include <stdio.h>
#define BinaryHeapValueType double

struct BinaryHeap
{
    int capacity;
    int size;
    BinaryHeapValueType* elements;
};

typedef struct BinaryHeap* BinaryHeapPointer;

BinaryHeapPointer binaryHeap_create(int capacity);
void binaryHeap_insert(BinaryHeapPointer bhp, BinaryHeapValueType value);
BinaryHeapValueType binaryHeap_deleteMin(BinaryHeapPointer bhp);

#endif /* BinaryHeap_h */

//
//  BinaryHeap.c
//  AVLTree
//
//  Created by sgf on 2017/8/26.
//  Copyright © 2017年 sgf. All rights reserved.
//

#include "BinaryHeap.h"
#include <stdlib.h>

#define START_VALUE 0


int binaryHeap_isFull(BinaryHeapPointer bhp)
{
    return bhp->size >= bhp->capacity;
}

BinaryHeapPointer binaryHeap_create(int capacity)
{
    BinaryHeapPointer bhp =  (struct BinaryHeap*)malloc(sizeof(struct BinaryHeap));
    bhp->capacity = capacity;
    bhp->size = 0;
    bhp->elements = malloc(sizeof(BinaryHeapValueType) * (capacity + 1));
    bhp->elements[0] = START_VALUE;
    
    return bhp;
}


void binaryHeap_insert(BinaryHeapPointer bhp, BinaryHeapValueType value)
{
    if(bhp==NULL)
    {
        return;
    }
    
    if(binaryHeap_isFull(bhp))
    {
        return;
    }
    
    if(bhp->size<=1)
    {
        bhp->elements[ ++bhp->size ] = value;
    }
    else
    {
        int i ;
        for ( i = ++bhp->size ;   bhp->elements[i/2] > value  ; i = i/2)
        {
            bhp->elements[i] = bhp->elements[i/2];
        }
        
        bhp->elements[i]  = value;
        
    }
    
    
}


BinaryHeapValueType binaryHeap_deleteMin(BinaryHeapPointer bhp)
{
    
    if(bhp==NULL)
    {
        return START_VALUE;
    }

    if(bhp->size == 0)
    {
        return  START_VALUE;
    }
    

    
    
    BinaryHeapValueType  minEl = bhp->elements[1];
    BinaryHeapValueType lastEl  = bhp->elements[bhp->size];
    bhp->size--;
    
    int i , subNode;
    for(i=1; i*2 <= bhp->size; i = subNode)
    {
    
        subNode = i * 2 ;
        if(subNode !=bhp->size   &&  bhp->elements[subNode] >  bhp->elements[subNode + 1] )
        {
            subNode++;
        }
        
        if(lastEl> bhp->elements[subNode])
            bhp->elements[i]  = bhp->elements[subNode] ;
        else
            break;
        
    }
    bhp->elements[i]  = lastEl;
    
    return minEl;
}





//----------应用----------
//-----------------------
//-----------------------
//-----------------------


//将所有元素移除,并在数组中实现排序
void binaryHeap_sort2Desc(BinaryHeapPointer bhp)
{
    
    while (bhp->size>0) {
        BinaryHeapValueType v = binaryHeap_deleteMin(bhp);
        bhp->elements[bhp->size + 1] = v;
    }
}




//根据一个数组,创建一个二叉堆
void binaryHeap_createWithArray_sort(int a[], int len, int index)
{
    //根节点
    if(index > len/2+1)
    {
        return;
    }
    
    //左下最大
    if(  a[ index * 2 ] < a[index] && a[index * 2 ] <  a[index * 2 + 1 ] )
    {
        int tmp = a[index];
        a[index] = a[index * 2];
        a[index * 2] = tmp;
        binaryHeap_createWithArray_sort(a, len, index * 2);
    }
    
    //右下最大
    else if(  a[ index * 2 + 1  ] < a[index] && a[index * 2  + 1] <  a[index * 2  ] )
    {
        int tmp = a[index];
        a[index] = a[index * 2 + 1];
        a[index * 2  + 1] = tmp;
        
        binaryHeap_createWithArray_sort(a, len, index * 2 + 1);
    }
    
}
发表评论?

0 条评论。

发表评论


注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>