调整第2个非叶节点为有序堆,则序号为i的节点的爹妈结点为(i-1)/2

堆排序

堆排序,堆排序复杂度

堆排序是依照二叉树。n个根本字体系Kl,K2,…,Kn称为(Heap),当且仅当该种类满意如下性质(简称为堆性质):

(1)ki<=k(2i)且ki<=k(2i+1)(1≤i≤
n/2),当然,那是小根堆,大根堆则换到>=号。//k(i)约等于二叉树的非叶子结点,K(2i)则是左子节点,k(2i+1)是右子节点。

堆排序的几个关键点:

一 、三个节点的八个子节点已经是有序堆,调整那一个节点为有序堆(递归调整);

贰 、制造堆:调整第一个非叶节点为平稳堆,逐级升高,直到一切数组为平稳堆。

三 、堆顶与终极叁个叶子节点交流,堆变小,再调动堆,再交替,直到堆大小为1,排序完结。

沾满代码:

#include "stdafx.h"
#include <stdio.h>

/*
 * L     初始无序堆
 * n     节点序号
 * size  无序堆节点个数
 */
void Heapify(int L[], int n, int size)
{
    int rchild=2*n+1;
    int lchild=2*n;
    if (rchild<=size)
    {
        int max=L[lchild]>L[rchild] ? lchild : rchild;
        if (L[n]<L[max])
        {
            int temp=L[n];
            L[n]=L[max];
            L[max]=temp;
            Heapify(L,max,size);
        }
    }
    else if (lchild==size)
    {
        if (L[n]<L[lchild])
        {
            int temp=L[n];
            L[n]=L[lchild];
            L[lchild]=temp;
        }
    }
}

// 建堆(大根堆)
void BuildHeap(int L[], int size)
{
    for (int i=size/2; i>0; i--) // 从最低层的节点开始创建有序堆,直到整个堆是有序堆。
    {
        Heapify(L,i,size);
    }
}

// L[0]是暂存区
void HeapSort(int L[], int size)
{
    BuildHeap(L,size);
    for (int i=size; i>0; i--)
    {
        L[0]=L[1];
        L[1]=L[i];
        L[i]=L[0];
        Heapify(L,1,i-1);
    }
}

int main(int argc, char* argv[])
{
    // 待排序数据不包括L[0]
    int L[13]={5,1,7,2,90,6,-5,23,10,4,50,12,5};
    int i=0;
    for (i=1; i<13; i++)
    {
        printf("%5d",L[i]);
    }
    printf("\n");

    HeapSort(L,12);

    for (i=1; i<13; i++)
    {
        printf("%5d",L[i]);
    }
    printf("\n");

    return 0;
}

 

http://www.bkjia.com/cjjc/1017050.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1017050.htmlTechArticle堆排序,堆排序复杂度
堆排序是依照二叉树。n个重庆大学字类别Kl,K2,,Kn称为(Heap),当且仅当该系列知足如下性质(简称为堆性质):…


堆定义
n个关键字系列Kl,K2,…,Kn称为(Heap),当且仅当该系列满意如下性质(简称为堆性质):
(1)ki<=k(2i)且ki<=k(2i+1)(1≤i≤
n),当然,那是小根堆,大根堆则换来>=号。//k(i)也就是二叉树的非叶结点,K(2i)则是左孩子,k(2i+1)是右孩子
若将此行列所蕴藏的向量奥迪Q5[1..n]作为是一棵完全二叉树的积存结构,则堆实质上是满意如下性质的完全二叉树:

1.学问互补


树中任一非叶结点的第壹字均不超出(或不低于)其左右孩子(若存在)结点的机要字。

1.0 完全二叉树

一棵深度为K,有n个节点的二叉树,对树中节点依照从上至下,从左至右的相继实行编号,要是编号为i(1<=i<=n)与满二叉树的号码为i的地方一致,则称此树为完全二叉树。

图片 1

一齐二叉树和非完全二叉树示意图.jpg

图片 2

1.1满二叉树

满二叉树:假如一棵二叉树全部支行都存在左右子节点,且独具的纸牌节点都在一如既往层,则成那棵树为满二叉树。

图片 3

满二叉树(a)与非满二叉树(b).jpg

【例】关键字连串(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满意堆性质(1)和(2),故它们均是堆,其相应的一点一滴二叉树分别如小根堆示例和大根堆示例所示。
大根堆和小根堆:根结点(亦称作堆顶)的最重要字是堆里富有结点关键字中最小者的堆称为小根堆,又称最小堆。根结点(亦称作堆顶)的重中之重字是堆里有着结点关键字中最大者,称为大根堆,又称最大堆。注意:①堆中任一子树亦是堆。②上述研讨的堆实际上是二叉堆(Binary
Heap),类似地可定义k叉堆。

1.2 完全二叉树的属性(重点)

假如对持有n个节点二叉树的根节点从0开头编号,则序号为i的节点的二老结点为(i-1)/2,左孩子的号码为2i+1,右孩子为2i+2。借使从1起来编号,则双亲结点编号为i/2,左孩子结点序号为2i,右孩子结点序号为2i+1.

高度
堆能够被看做是一棵树,结点在堆中的中度能够被定义为从本结点到叶子结点的最长简单下落路径下边包车型客车数量;定义堆的惊人为树根的惊人。我们将看到,堆结构上的某些基本操作的运作时刻至多是与树的冲天成正比,为O(lgn)。

2 堆(千呼万唤始出来)

堆:n个根本字种类Kl,K2,…,Kn称为(Heap),当且仅当该体系满意如下性质(简称为堆性质):
(1)ki<=k(2i)且ki<=k(2i+1)(1≤i≤
n/2),当然,那是小根堆,大根堆则换来>=号。//k(i)相当于二叉树的非叶子结点,K(2i)则是左子节点,k(2i+1)是右子节点
若将此行列所蕴藏的向量PAJERO[1..n]用作是一棵一齐二叉树的储存结构,则堆实质上是满意如下性质的通通二叉树:

图片 4

树中任一非叶子结点的严重性字均不超出(或非常的大于)其左右子女(若存在)结点的基本点字。

 

3.堆得建立


算法思路:
1.大家首先将数组举行早先化调整成大根堆。
2.然后拓展排序,每一回排序时,将最终2个序号n节点的值与根节点0的值实行沟通,然后将节点又调整成堆。
3.然后将根节点与n-1举办置换重复步骤2。直到类别为平稳

package basic.sort;

import java.util.Arrays;
import java.util.Random;

public class HeapSort {
    /*
     * 将数组调整为小根堆,即由小到大排序,每次对定的数据移动到当前为排序的数据列的最后,记得到从小到大的排序数组
     */

    /*
     * 创建堆(对该堆进行简单的排序)
     */
    public <AnyType extends Comparable<? super AnyType>>
    void CreateHeap(AnyType[] heap) {
        for (int i = heap.length /2 ; i >=  0 ; i--) {
            AdjustHeap(heap ,i, heap.length);
        }
    }

    /*
     * 调整堆使其堆顶为未排序堆中最大关键字
     */
    public <AnyType extends Comparable<? super AnyType>>
    void AdjustHeap(AnyType[] heap, int location, int unSortlength) {
        AnyType temp;
        int right;
        /*
         * 确保左右节点存在
         */
        if ((right = (location + 1) * 2) < unSortlength) {
            /*
             * 判断左右节点大小
             */
            if (heap[right].compareTo(heap[right - 1]) > 0) {
                /*
                 * 判断父节点与子节点的大小,若父节点小,则与大的子节点换位
                 */
                if (heap[location].compareTo(heap[right]) < 0) {
                    temp = heap[location];
                    heap[location] = heap[right];
                    heap[right] = temp;
                    /*
                     * 递归法对换位后的子节点及其子节点进行调整
                     */
                    AdjustHeap(heap,right, unSortlength);
                }
            } else {
                /*
                 * 左节点大于右节点
                 */
                if (heap[location].compareTo(heap[right - 1]) < 0) {
                    temp = heap[location];
                    heap[location] = heap[right - 1];
                    heap[right - 1] = temp;
                    /*
                     * 递归法对换位后的子节点及其子节点进行调整
                     */
                    AdjustHeap(heap ,right - 1, unSortlength);
                }
            }
        }
        /*
         * 确保左节点存在
         */
        else if ((right = (location + 1) * 2 - 1) < unSortlength) {
            /*
             * 与左节点进行比较
             */
            if (heap[location].compareTo(heap[right]) <0) {
                /*
                 * 左子节点大于父节点,将两者进行换位
                 */
                temp = heap[location];
                heap[location] = heap[right];
                heap[right] = temp;
                AdjustHeap(heap ,right, unSortlength);
            }
        }
    }
    public static void main(String[] args) {

        Random rand = new Random();
        Integer[] heap = new Integer[10];
        for(int i = 0 ;i <10 ;i++){
            heap[i] = rand.nextInt(1000);
        }
        println(Arrays.toString(heap));

        HeapSort heapSort = new HeapSort();


        /*
         * 创建堆(对该堆进行简单的排序)
         */
        heapSort.CreateHeap(heap);
        Integer temp ;
        for (int i = heap.length - 1; i > 0; i--){
            temp = heap[0];
            heap[0] = heap[i];
            heap[i] = temp;
        /*
         *  从堆顶进行调整,使未排序堆中最大关键字到堆顶
             */
            heapSort.AdjustHeap(heap ,0, i);
        }

        println(Arrays.toString(heap));
    }

    public static void println(String str){
        System.out.println(str);        
    }
}

3.1以大根堆为例:

 /**
     * 堆调整算法
     * @param num   数组
     * @param s 调整节序号
     * @param l 数组排序最大的序号 
     */
  public static void HeapAdjust(int[] num,int s,int l){
      int i,j;
      int temp=num[s];
      i=s;
      // 根据二叉树的性质可知道每一个序号对应的子节点以及双亲节点
      for(j=2*i+1;j<=l;j=2*j+1){
          //判断如果j指向数值较大的节点
          if(j<l&&num[j]<num[j+1]){
              j=j+1;
          }
          //如果调整节点大于其子节点最大的值则无需调整
          if(temp>num[j]){
              break;
          }
          //如果小于则将子节点移动到根节点位置,如果还存在子节点则继续判断调整位置的子节点
          //准备继续向下 调整节点
          num[i]=num[j];
          i=j;
      }
      //最后插入数据
      num[i]=temp;
  }                             

 

3.2堆的确立

   /**
     * 堆建立初始化函数
     * @param nums 数组序列
     * @param l 最大序号
     */
  public static void HeapInit(int[] nums,int l){
      for (int i = (l-1) / 2; i >=0; i--) {
          HeapAdjust(nums, i, l);
      }
  }

引进互联网财富C++达成

3.3 堆的排序算法

  public static void HeapSort(int[] nums,int l){
     for(int i=l;i>0;i--){
         int temp=nums[0];
         nums[0]=nums[i];
         nums[i]=temp;
         //因为每次调整都是对根节点进行调整所以下列方法s永远为0
         HeapAdjust(nums,0,i-1);
     }
  }

http://blog.csdn.net/clam\_clam/article/details/6799763

3.4最后我们来看望效果

 public static void main(String[] args){
        int[] nums={3,2,4,9,8};
        //第一步根据节点创建堆
        for (int i = (4-1) / 2; i >=0; i--) {
            HeapAdjust(nums, i, 4);
        }
        //第二步排序
        HeapSort(nums,4);
        for(int n:nums){
            System.out.println(n);
        }

    }

 

输出

2
3
4
8
9

相关文章