Lmsgsendnilself

Uninhibited Soul, Free Craziness

最大堆

| Comments

  由于最近在项目中用到了最大堆的思想来处理一个事件集,因此专门用iOS实现了一下最大堆的代码。   首先,我们看一下堆的定义:
  n个元素的序列{k1,k2,…,kn},当且仅当满足如下关系时被成为堆
    (1)Ki <= k2i 且 ki <= k2i+1

  或 (2) Ki >= k2i 且 ki >= k2i+1
             (i = 1,2,…[n/2])
  当满足(1)时,为最小堆,当满足(2)时,为最大堆。

  了解堆特点之后,不要急着动手,捋一下写一个堆的封装,需要的主要接口。对于堆,我们很容易联想到类似的数据结构,譬如队列,栈等,这些数据结构基本上外部需要暴露init,push, pop ,count这几个方法,而内部针对堆的特性,需要对push和pop的调整进行自底而上和自顶而下两种有区别的调整策略,所以还需要两调整方法。
  首先实现初始化方法,当然需要在初始化方法中shenqi由于我们的数据并不是简单的例如double,int这种基本数据类型,而是一个较为复杂一点的model。因此,对于初始化方法需要添加一个闭包的比较器,以便更方便的对任何数据进行比较。

1
2
3
4
5
6
7
8
- (id)initWithComparator:(NSComparator)comparator{

    if (self = [super init]) {
        _comparator = [comparator copy];
        _items = [[NSMutableArray alloc] init];
    }
    return self;
}

  对于push和pop方法,简单的实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
- (void)pushHeap:(id)obj{

    [self.items addObject:obj];

    [self adjustHeapFromDownToUp];
}

- (id)popHeap{

    if ([self.items count] == 0) {
        return nil;
    }
    id obj = [self.items objectAtIndex:0];
    if (self.items.count > 1) {
        id lastObj = [self.items lastObject];
        [self.items replaceObjectAtIndex:0 withObject:lastObj];
    }
    [self.items removeLastObject];
    [self adjustHeapFromUpToDown:0];
    return obj;
}

  接下来说下调整堆的两个方法的思路,

  自顶而下主要思路就是:
    1 将需要调整的节点i的左右子节点2i+1和2i+2进行比较,获取较大的节点,
    2 将需要调整的节点i和较大的节点进行比较。(1) 如果后者大,则交换两个数据的位置,并从需要调整的节点的新的位置进行下一轮比较,直到完全符合堆特性;(2) 如果前者大,说明已经符合最大堆特性,则直接break出迭代循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
- (void)adjustHeapFromUpToDown:(int)index{

    NSInteger count = [self count];
    if (index < 0 || (index >= count)) {
        return;
    }
    id top = [self.items objectAtIndex:index];
    int parent = index;
    int child = 2 * parent + 1;
    while (child < count) {
        int right = child + 1;
        if (right < count) {
        //get bigger subNode
            if (_comparator([self.items objectAtIndex:child], [self.items objectAtIndex:right]) == NSOrderedAscending) {
                child = right;
            }
        }
      // compare  bigger subNode with needing adjusting node and adjust
        if (_comparator(top, [self.items objectAtIndex:child]) == NSOrderedAscending) {
            [self.items replaceObjectAtIndex:parent withObject:[self.items objectAtIndex:child]];
        } else {
            break;
        }
        parent = child;
        child = 2 * parent + 1;
    }
    if (parent != index) {
        [self.items replaceObjectAtIndex:parent withObject:top];
    }
}


  自底而上的主要思路就是:
    1 将需要调整的节点i和其父节点(i-1)/2进行比较,如果父节点大,说明不需要调整,则直接break,不再执行;如果需要调整的节点i大,则直接交换,并从需要调整的节点的新位置进行新的一轮比较,直到完全符合对特性为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
- (void)adjustHeapFromDownToUp{

    NSInteger count = [self.items count];
    NSInteger child = count - 1;
    NSInteger parent = (child - 1) / 2;
    id obj = [self.items objectAtIndex:child];
    while (child > 0) {

      //compare needing adjusting node with superNode and adjust
        if (_comparator(obj, [self.items objectAtIndex:parent]) == NSOrderedAscending) {
            break;
        }
        [self.items replaceObjectAtIndex:child withObject:[self.items objectAtIndex:parent]];
        child = parent;
        parent = (child - 1) / 2;
    }

    if (child < count - 1) {
        [self.items replaceObjectAtIndex:child withObject:obj];
    }
}

Comments