IOS开发算法 堆排序 【附代码】

今天爱分享给大家带来IOS开发算法 堆排序 【附代码】,希望能够帮助到大家。

堆(英语:heap)是计算机科学中一类特殊的数据结构的统称
堆总是满足下列性质: 1. 堆中某个节点的值总是不大于或不小于其父节点的值; 2. 堆总是一棵完全二叉树
将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆
完全二叉树
若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

/**
 时间复杂度为O(nlogn)
 */
- (void)heapSortArray:(NSMutableArray *)heapList len:(NSInteger)len {
    // 建立堆,从最底层的父节点开始
    for(NSInteger i = (heapList.count/2 -1); i>=0; i--)
        [self adjustHeap:heapList location:i len:heapList.count];
    
    for(NSInteger i = heapList.count -1; i >= 0; i--){
        NSInteger maxEle = ((NSString *)heapList[0]).integerValue;
        heapList[0] = heapList[i];
        heapList[i] = @(maxEle).stringValue;
        
        [self adjustHeap:heapList location:0 len:i];
    }
}

- (void)adjustHeap:(NSMutableArray *)heapList location:(NSInteger)p len:(NSInteger)len {
    NSInteger curParent = ((NSString *)heapList[p]).integerValue;
    NSInteger child = 2*p + 1;
    while (child < len) {
        // left < right
        if (child+1 < len && ((NSString *)heapList[child]).integerValue < ((NSString *)heapList[child+1]).integerValue) {
            child ++;
        }
        if (curParent < ((NSString *)heapList[child]).integerValue) {
            heapList[p] = heapList[child];
            p = child;
            child = 2*p + 1;
        }
        else
            break;
    }
    heapList[p] = @(curParent).stringValue;
}

人已赞赏
IOS

IOS开发算法 快速排序 【附代码】

2020-10-23 11:21:10

IOS

IOS开发算法 归并排序【附代码】

2020-10-23 11:24:31

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧