# 用c语言手写堆排序以及来道简单题吧 1046. 最后一块石头的重量

2021/01/01 11:48

## 堆排序手写一遍吧

#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;
}



0
0 收藏

0 评论
0 收藏
0