用c语言手写堆排序以及来道简单题吧 1046. 最后一块石头的重量
程序员文章站
2022-06-23 10:07:25
堆排序手写一遍吧#include#includevoid swap(int *a,int *b){int temp=*a;*a=*b;*b=temp; } void HeapAdjust(int *heap,int i,int size){int lchild=2*i+1;//左孩子序号 int rchild=2*i+2;//右孩子序号int temp =i;if(i<=size/2-1){...
堆排序手写一遍吧
#include<stdio.h>
#include<stdlib.h>
void swap(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
void HeapAdjust(int *heap,int i,int size)
{
int lchild=2*i+1;//左孩子序号
int rchild=2*i+2;//右孩子序号
int temp =i;
if(i<=size/2-1)
{
if(lchild<=size-1&&heap[lchild]>heap[temp])
{
temp=lchild;
}
if(rchild<=size-1&&heap[rchild]>heap[temp])
{
temp=rchild;
}
if(temp!=i)
{
swap(&heap[i],&heap[temp]);
HeapAdjust(heap,temp,size);//避免交换后的子树不满足堆
}
}
}
void BuildHeap(int *heap,int size)
{
int i;
for(i=size/2-1;i>=0;i--)
{
HeapAdjust(heap,i,size);
}
}
void HeapSort(int *heap,int size)
{
int i;
BuildHeap(heap,size);
for(i=size-1;i>=0;i--)
{
swap(&heap[0],&heap[i]);//每次将最大的丢在数组末尾,实现排序
HeapAdjust(heap,0,i-1);//将剩余结点重新调整成大顶堆
}
}
Leetcode例题 1046. 最后一块石头的重量
解法
void swap(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
void HeapAdjust(int *heap, int i,int size)
{
int lchild=2*i+1;//左孩子序号
int rchild=2*i+2;//右孩子序号
int temp =i;
if(i<=size/2-1)
{
if(lchild<=size-1&&heap[lchild]>heap[temp])
{
temp=lchild;
}
if(rchild<=size-1&&heap[rchild]>heap[temp])
{
temp=rchild;
}
if(temp!=i)
{
swap(&heap[i],&heap[temp]);
HeapAdjust(heap,temp,size);//避免交换后的子树不满足堆
}
}
}
void buildHeap(int *heap, int size) {
for (int i=size-1; i>=0; --i) {
HeapAdjust(heap, i, size);
}
}
int fetch(int *heap, int *size) {
int x = heap[0];
heap[0] = heap[--(*size)];
HeapAdjust(heap, 0, *size);
return x;
}
void push(int *heap, int *size, int x) {
heap[(*size)++] = x;
HeapAdjust(heap, *size-1, *size);
}
int lastStoneWeight(int* stones, int stonesSize){
buildHeap(stones, stonesSize);
while (stonesSize > 1) {
int x = fetch(stones, &stonesSize);
int y = fetch(stones, &stonesSize);
if (x == y) {
// do nothing
} else {
int t = abs(x-y);
push(stones, &stonesSize, t);
}
}
return stonesSize ? stones[0] : 0;
}
本文地址:https://blog.csdn.net/qazwsxxxxxasd/article/details/111999595
上一篇: Kotlin与Java的区别详解
下一篇: Android小项目--2048小游戏