最大堆
最大堆的存储结构-完全二叉树，数组存储
typedef struct HeapStruct
*MaxHeap
;
struct HeapStruct
{
ElementType
*Elements
;
int Size
;
int Capacity
;
};
最大堆操作
MaxHeap
Create( int maxsize
){
MaxHeap H
= (MaxHeap
)malloc(sizeof(struct HeapStruct
));
H
->Elements
= (ElementType
*)malloc( (MaxSize
+1)*sizeof(ElementType
));
H
->Size
= 0;
H
->Capacity
= maxsize
;
H
->Elements
[0] = MaxData
;
return H
;
}
void Insert
( MaxHeap H
, ElementType item
){
int i
;
if ( IsFull(H
) ) {
printf("The max heap is full.\n");
return;
}
i
= ++H
->Size
;
for ( ; H
->Elements
[i
/2] < item
; i
/=2 )
H
->Elements
[i
] = H
->Elements
[i
/2];
H
->Elements
[i
] = item
;
}
ElementType DeleteMax
( MaxHeap H
){
int Parent
, Child
;
ElementType MaxItem
, temp
;
if ( IsEmpty(H
) ) {
printf("The max heap is empty.\n");
return;
}
MaxItem
= H
->Elements
[1];
temp
= H
->Elements
[H
->Size
--];
for ( Parent
=1; Parent
*2<=H
->Size
; Parent
=Child
){
Child
= Parent
*2;
if ( (Child
!=H
->Size
) && (H
->Elements
[Child
] < H
->Elements
[Child
+1]))
Child
++;
if ( temp
>= H
->Elements
[Child
])
break;
else
H
->Elements
[Parent
] = H
->Elements
[Child
];
}
H
->Elements
[Parent
] = temp
;
return MaxItem
;
}
bool IsFull
( MaxHeap H
){
if ( H
->Size
== H
->Capacity
)
return true
;
else
return false
;
}
bool IsEmpty
( MaxHeap H
){
if ( H
->Size
== 0 )
return true
;
else
return false
;
}
void LevelOrderTraversal
( MaxHeap H
) {
int i
;
printf("Level Order Search: ");
for ( i
=1; i
<=H
->Size
; i
++){
printf("]", H
->Elements
[i
]);
}
printf("\n");
}
参考自 https://www.icourse163.org/learn/ZJU-93001?tid=120001#/learn/content
