heapsort.h

Author

Zhu Dengda (zhudengda@mail.iggcas.ac.cn)

Date

2023-03

  非标准版本的最小推排序，堆元素本身数据是某个数据节点的索引值，
  判断元素大小关系使用节点对应的走时进行比较

Typedefs

typedef MYINT HEAP_DATA

Functions

void MinHeap_AdjustUp(HEAP_DATA *HEAP_data, MYINT child, MYINT *NroIdx, const MYREAL *TT)

最小堆向上调整

参数:

• HEAP_data – (inout)指向堆首的指针

• child – (in)某个堆元素在堆中的索引值

• NroIdx – (out)一维指针，用于在节点索引位置处填上堆中的索引值

• TT – (in)一维指针，记录每个节点的走时

void MinHeap_AdjustDown(HEAP_DATA *HEAP_data, MYINT size, MYINT root, MYINT *NroIdx, const MYREAL *TT)

最小堆向下调整

参数:

• HEAP_data – (inout)指向堆首的指针

• size – (in)堆大小

• root – (in)某个堆元素在堆中的索引值

• NroIdx – (out)一维指针，用于在节点索引位置处填上堆中的索引值

• TT – (in)一维指针，记录每个节点的走时

HEAP_DATA HeapPop(HEAP_DATA *HEAP_data, MYINT *psize, MYINT *NroIdx, const MYREAL *TT)

从堆首弹出元素，即返回堆首元素并且从堆中删除堆首，并做一次向下调整堆

参数:

• HEAP_data – (inout)指向堆首的指针

• psize – (inout)堆大小，会被调整大小

• NroIdx – (out)一维指针，用于在节点索引位置处填上堆中的索引值

• TT – (in)一维指针，记录每个节点的走时

返回:

堆首元素

HEAP_DATA *HeapPush(HEAP_DATA *HEAP_data, MYINT *psize, MYINT *pcap, HEAP_DATA newdata, MYINT *NroIdx, const MYREAL *TT)

从堆尾压入元素，即添加元素，并做一次向上调整堆

参数:

• HEAP_data – (inout)指向堆首的指针

• psize – (inout)堆大小，会被调整大小

• pcap – (inout)堆最大容量，视情况会被调整大小

• newdata – (in)新元素

• NroIdx – (out)一维指针，用于在节点索引位置处填上堆中的索引值

• TT – (in)一维指针，记录每个节点的走时

返回:

堆首指针

void HeapBuild(HEAP_DATA *HEAP_data, MYINT size, MYINT idx, MYINT *NroIdx, const MYREAL *TT)

建立堆

参数:

• HEAP_data – (inout)指向堆首的指针

• size – (in)堆大小

• idx – (in)指定子堆的索引，完全建立堆则idx==size

• NroIdx – (out)一维指针，用于在节点索引位置处填上堆中的索引值

• TT – (in)一维指针，记录每个节点的走时

inline void Swap(HEAP_DATA *data1, HEAP_DATA *data2)

交换数据（内联函数）

参数:

• data1 – 数据1的指针

• data2 – 数据2的指针

void print_HEAP(HEAP_DATA *data, MYINT size, MYINT nr, MYINT nt, MYINT np, MYINT *NroIdx, MYREAL *TT, MYREAL *gTr, MYREAL *gTt, MYREAL *gTp)

打印推数据【用于debug】