算法-優先隊列與堆排序

我們自己每天使用的電腦能同時運行多個應用程序，沒有感覺到卡頓，電腦為每個應用程序的事件分配了一個優先級，移動端的手機也是，通常不管我們是 在看電影，發短信只要有電話，電話絕對是優先級最高的。這個時候我們需要一種合理的數據結構刪除最大元素和插入元素，我們可以稱之為優先隊列。實現這種優 先隊列最合適的數據結構可以通過經典的二叉堆來實現，相對于其他數據結構更高效。

優先隊列

開始擼代碼之前我們需要明白幾個概念:

1.當一棵二叉樹的每個節點都大于等于等于它的兩個子節點時，它稱之為堆有序。

2.二叉堆是一組能夠用堆有序的完全二叉樹排序的元素，并在數組中按照層級存儲。

在一個堆中，索引為index的節點的父節點的位置是index/2,子節點的位置為2*index和2*index+1，用數組實現一個完全二叉樹的插入元素和刪除最大元素是非常簡潔的。

核心代碼:

-(void)insert:(NSString *)value{
  [self.dataSource  addObject:value];
  self.maxIndex=self.maxIndex+1;
  [self swimUp:self.maxIndex];
}
-(void)deleteMax{
  [self swap:1 secondIndex:self.maxIndex];//第一個節點和最后一個節點進行交換
  [self.dataSource removeObjectAtIndex:self.maxIndex--];//刪除最后的節點
  [self sinkDown:1];//恢復堆的有序性
}
-(void)swimUp:(NSInteger)index{
  //父節點小于當前的子節點
  while (index>1&&[self lessCompare:index/2 secondIndex:index]) {
    [self swap:index/2 secondIndex:index];
    index=index/2;
  }
}
-(void)sinkDown:(NSInteger)index{
  while (2*index<=self.maxIndex) {
    NSInteger  i=2*index;
    //左右節點大小判斷
    if (i<self.maxIndex&&[self lessCompare:i secondIndex:i+1]) {
      i++;
    }
    if (![self lessCompare:index secondIndex:i]) break;
    [self swap:index secondIndex:i];
    index=i;
  }
}
-(BOOL)lessCompare:(NSInteger)firstIndex secondIndex:(NSInteger)secondIndex{
  return [[self.dataSource objectAtIndex:firstIndex] integerValue]<[[self.dataSource objectAtIndex:secondIndex] integerValue];
}
-(void)swap:(NSInteger)firstIndex secondIndex:(NSInteger)secondIndex{
  NSString  *temp=[self.dataSource objectAtIndex:firstIndex];
  self.dataSource[firstIndex]=[self.dataSource objectAtIndex:secondIndex];
  self.dataSource[secondIndex]=temp;
}

PriorityQueue  *queue=[[PriorityQueue alloc]init];
  NSMutableArray *arr=[[NSMutableArray alloc]initWithCapacity:10];
  [arr addObject:[NSNull null]];
  [arr addObject:@"8"];
  [arr addObject:@"5"];
  [arr addObject:@"6"];
  [arr addObject:@"2"];
  [arr addObject:@"3"];
  [arr addObject:@"4"];
  queue.dataSource=arr;
  queue.maxIndex=[arr count]-1;
  [queue insert:@"7"];
//  [queue deleteMax];
  for (NSInteger i=1; i<[queue.dataSource count]; i++) {
      NSLog(@"數值:%@",queue.dataSource[i]);
  }
  NSLog(@"iOS技術交流群:228407086");
  NSLog(@"原文地址:http://www.cnblogs.com/xiaofeixiang");

測試結果:

堆有序

上面的Demo中從最開始就是堆有序的，但是很多情況我們是一個無序的堆，需要自己重新構造排序，分為兩步:

1.首先將堆變成一個大根堆，也就是最大堆。

2. 重復刪除最大元素，最后的元素和第一個進行交換，然后進行下沉操作(和有序堆中刪除元素的方式一樣)。

-(void)sort{
  NSInteger count=[self.dataSource count]-1;
  for (NSInteger k=count/2; k>=1; k--) {
    [self sinkSort:k count:count];
  }
  while (count>1) {
    [self swap:1 secondIndex:count--];
    [self sinkSort:1 count:count];
  }
}
-(void)sinkSort:(NSInteger)index count:(NSInteger)count{
  while (2*index<=count) {
    NSInteger  i=2*index;
    //左右節點大小判斷
    if (i<count&&[self lessCompare:i secondIndex:i+1]) {
      i++;
    }
    if (![self lessCompare:index secondIndex:i]) break;
    [self swap:index secondIndex:i];
    index=i;
  }
}

PriorityQueue  *queue=[[PriorityQueue alloc]init];
        NSMutableArray *arr=[[NSMutableArray alloc]initWithCapacity:10];
        [arr addObject:[NSNull null]];
        [arr addObject:@"1"];
        [arr addObject:@"2"];
        [arr addObject:@"3"];
        [arr addObject:@"4"];
        [arr addObject:@"5"];
        [arr addObject:@"6"];
        [arr addObject:@"7"];
        queue.dataSource=arr;
        queue.maxIndex=[arr count]-1;
        [queue sort];
        for (NSInteger i=1; i<[queue.dataSource count]; i++) {
            NSLog(@"數值:%@",queue.dataSource[i]);
        }
        NSLog(@"iOS技術交流群:228407086");
        NSLog(@"原文地址:http://www.cnblogs.com/xiaofeixiang");