无为

无为则可为,无为则至深!

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  190 Posts :: 291 Stories :: 258 Comments :: 0 Trackbacks
Heap sort
       
import java.io.IOException;

class MyNode {
  private int iData; 

  public MyNode(int key) {
    iData = key;
  }

  public int getKey() {
    return iData;
  }

}

public class Heap {
  private MyNode[] heapArray;

  private int maxSize;

  private int currentSize; // number of items in array

  public Heap(int mx) {
    maxSize = mx;
    currentSize = 0;
    heapArray = new MyNode[maxSize];
  }

  public MyNode remove() 
  
    MyNode root = heapArray[0];
    heapArray[0= heapArray[--currentSize];
    trickleDown(0);
    return root;
  }

  public void trickleDown(int index) {
    int largerChild;
    MyNode top = heapArray[index]
    while (index < currentSize / 2)
    {
      int leftChild = * index + 1;
      int rightChild = leftChild + 1;
      // 找到最大的子节点
      if (rightChild < currentSize
          && 
          heapArray[leftChild].getKey() < heapArray[rightChild]
              .getKey())
        largerChild = rightChild;
      else
        largerChild = leftChild;

      if (top.getKey() >= heapArray[largerChild].getKey())
        break;

      heapArray[index= heapArray[largerChild];
      index = largerChild; 
    }
    heapArray[index= top;
  }

  public void displayHeap() {
    int nBlanks = 32;
    int itemsPerRow = 1;
    int column = 0;
    int currentIndex = 0
    while (currentSize > 0)
    {
      if (column == 0
        for (int k = 0; k < nBlanks; k++)
          System.out.print(' ');
      System.out.print(heapArray[currentIndex].getKey());

      if (++currentIndex == currentSize//  判断是否输出结束
        break;

      if (++column == itemsPerRow// 是否到达行尾?
      {
        nBlanks /= 2
        itemsPerRow *= 2
        column = 0
        System.out.println()
      else
        for (int k = 0; k < nBlanks * 2; k++)
          System.out.print(' ')// 输入空白
    
  }

  public void displayArray() {
    for (int j = 0; j < maxSize; j++)
      System.out.print(heapArray[j].getKey() " ");
    System.out.println("");
  }

  public void insertAt(int index, MyNode newNode) {
    heapArray[index= newNode;
  }

  public void incrementSize() {
    currentSize++;
  }

  public static void main(String[] argsthrows IOException {
    int size, i;

    size = 100;
    Heap theHeap = new Heap(size);

    for (i = 0; i < size; i++) {
      int random = (int) (java.lang.Math.random() 100);
      MyNode newNode = new MyNode(random);
      theHeap.insertAt(i, newNode);
      theHeap.incrementSize();
    }

    System.out.print("Random: ");
    theHeap.displayArray();
    for (i = size / 1; i >= 0; i--)
      theHeap.trickleDown(i);

    System.out.print("Heap:   ");
    theHeap.displayArray();
    theHeap.displayHeap();
    for (i = size - 1; i >= 0; i--) {
      MyNode biggestNode = theHeap.remove();
      theHeap.insertAt(i, biggestNode);
    }
    System.out.print("Sorted: ");
    theHeap.displayArray();
  }
}



凡是有该标志的文章,都是该blog博主Caoer(草儿)原创,凡是索引、收藏
、转载请注明来处和原文作者。非常感谢。

posted on 2007-09-28 14:24 草儿 阅读(1527) 评论(0)  编辑  收藏 所属分类: java

只有注册用户登录后才能发表评论。


网站导航: