C语言数据结构-排序-堆辅助函数

「爱情、让人受尽委屈。」 2022-10-07 11:46 184阅读 0赞

# 堆辅助函数 #

二叉堆是完全二叉树或者是近似完全二叉树。二叉堆有两种：最大堆和最小堆。

*  最大堆(大顶堆)：父结点的键值总是大于或等于任何一个子节点的键值，即最大的元素在顶端；
 *  最小堆(小顶堆)：父结点的键值总是小于或等于任何一个子节点的键值，即最小的元素在顶端。
 *  二叉堆子结点的大小与其左右位置无关。

二叉堆一般用数组来表示。例如，根节点在数组中的位置是0，第n个位置的子节点分别在2n+1和 2n+2。 因此，第0个位置的子节点在1和2，1的子节点在3和4。以此类推。这种存储方式便于寻找父节点和子节点。在二叉堆上可以进行插入节点、删除节点、取出值最小的节点、减小节点的值等基本操作。

“最小堆”的定义如下：

typedef struct _otherInfo
    {
        int i;
        int j;
    }OtherInfo;
    
    typedef struct _minHeapNode
    {
        int value;
        OtherInfo otherInfo;
    }MinHeapNode, *PMinHeapNode;
    
    typedef struct _minPQ {
        PMinHeapNode heap_array; // 指向堆元素数组
        int heap_size; // 当前堆中的元素个数
        int capacity;  //堆数组的大小
    }MinHeap, *PMinHeap;

请实现最小堆的四个辅助函数：

int parent(int i); //返回堆元素数组下标为 i 的结点的父结点下标
    int left(int i);  //返回堆元素数组下标为 i 的结点的左子结点下标
    int right(int i);  //返回堆元素数组下标为 i 的结点的右子结点下标
    void swap_node(MinHeapNode *x, MinHeapNode *y);  //交换两个堆元素的值

### 提供代码 ###

#include <stdio.h>
    #include <stdlib.h>
    #include "minbinheap.h" // 请不要删除，否则检查不通过
    
    int parent(int i){
    
    }
    
    int left(int i){
    
    }
    
    int right(int i){
    
    }
    
    void swap_node(MinHeapNode *x, MinHeapNode *y){
    
    }

### 实例解读 ###

一个堆节点由三个组成部分

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70][]

### 参考答案 ###

#include<stdio.h>
    #include<stdlib.h>
    
    //子节点
    typedef struct _otherInfo
    {
    	int i;
    	int j;
    }OtherInfo;
    
    //堆元素
    typedef struct _minHeepNode
    {
    	int value;
    	OtherInfo otherInfo;
    }MinHeapNode,*PMinHeapNode;
    
    
    //最小堆
    typedef struct _minPQ
    {
    	PMinHeapNode heap_array;//指向堆元素的数组
    	int heap_size;	//堆元素的个数
    	int capacity;	//堆元素的容量
    }MinHeap,*PMinHeap;
    
    
    //返回堆元素的父节点下标
    //n->2n+1  2n+2
    int parent(int i) {
    	return (i-1) / 2;
    }
    
    //返回左子节点
    int left(int i){
    	return 2 * i + 1;
    }
    
    int right(int j) {
    	return 2 * j + 2;
    }
    
    //交换两个堆元素的值
    void swap_node(MinHeapNode* x, MinHeapNode* y) {
    	int value;
    	int i, j;
    
    	value = y->value;
    	i = y->otherInfo.i;
    	j = y->otherInfo.j;
    
    	y->value = x->value;
    	y->otherInfo.i = x->otherInfo.i;
    	y->otherInfo.j = x->otherInfo.j;
    
    	x->value = value;
    	x->otherInfo.i = i;
    	x->otherInfo.j = j;
    }
    
    int main()
    {
    	//创建堆
    	return 0;
    }

### 答案 ###

#include <stdio.h>
    #include <stdlib.h>
    #include "minbinheap.h" // 请不要删除，否则检查不通过
     
    //返回堆元素的父节点下标
    //n->2n+1  2n+2
    int parent(int i) {
    	return (i-1) / 2;
    }
    
    //返回左子节点
    int left(int i){
    	return 2 * i + 1;
    }
    
    int right(int j) {
    	return 2 * j + 2;
    }
    
    //交换两个堆元素的值
    void swap_node(MinHeapNode* x, MinHeapNode* y) {
    	int value;
    	int i, j;
    
    	value = y->value;
    	i = y->otherInfo.i;
    	j = y->otherInfo.j;
    
    	y->value = x->value;
    	y->otherInfo.i = x->otherInfo.i;
    	y->otherInfo.j = x->otherInfo.j;
    
    	x->value = value;
    	x->otherInfo.i = i;
    	x->otherInfo.j = j;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70]: /images/20221005/5f41235e42ef4708b2673cdf854b77eb.png