欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

用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. 最后一块石头的重量

用c语言手写堆排序以及来道简单题吧 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