使用堆排序算法

问题描述

Heaps的主要应用之一是Heap-Sort。它包含2个步骤



（1）构建堆和



（2）排序数组是通过重复删除最大元素创建（每次删除后更新堆以维护堆）。

One of the main application of Heaps is Heap-Sort. It consists of 2 steps

(1) Build the heap and

(2) Sorted array is created by repeatedly removing the largest element (Heap is updated after each removal to maintain the heap).

Input
	N
	x1 x2 ……… xn

其中，

where,

N is the total numbers to be sorted
 xi    input numbers

输出



y1 y2 ......... yn



数组y的排序方式





堆排序功能已经可供您使用



您需要完成构建堆和堆化功能







您需要编码以下功能

Output

y1 y2 ……… yn

where array y is sorted


Heap sort function is already made available to you

You need to complete the build heap and heapify function



You need to code the following functions

// function creates and build a heap using minHeapify

void createHeap(struct MinHeap* minHeap){

// Single Node is a heap   

    			// Start from bottom most and rightmost internal node and heapify all internal nodes in bottom up way

 

	}

// heapify a min Heap.

void heapify(struct MinHeap* minHeap, int idx){

// idx is the index of the node you want to heapify

}

我尝试过什么：

What I have tried:

void createHeap(struct MinHeap* minHeap)
{
    int i,numelems;
   // n=heap[0]; //no. of elements
    for(i=numelems/2;i>=1;i--)
        down_adjust(minHeap,i);
}

void heapify(int*a , int len)
{
 int item,i,j,k;
 
 for(k=1 ; k<len ; k++)
 {
  item = a[k];
  i = k;
  j = (i-1)/2;
 
  while( (i>0) && (item>a[j]) )
  {
   a[i] = a[j];
   i = j;
   j = (i-1)/2;
  }
  a[i] = item;
 }
}

推荐答案

这篇关于使用堆排序算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！