为HTML提供更多的结构,以便与选择器一起使用:
<div class="song">
<div>4</div>
</div>
<div class="song">
<div>2</div>
</div>
<div class="song">
<div>6</div>
</div>
<div class="song">
<div>3</div>
</div>
<div class="song">
<div>1</div>
</div>
<div class="song">
<div>1</div>
</div>
<div class="song">
<div>0</div>
</div>
O(n*logn)
allSongs = $("div.song").get();
allSongs.sort(function(a,b) {
a = $(a);
b = $(b);
// calling a.text() does only work if there's no text besides the rating.
if (a.text() > b.text()) {
return -1;
} else if (a.text() < b.text()) {
return 1;
} else {
return 0;
}
});
// hide all elements that have an index greater/equal to 5
$(allSongs.slice(5)).hide();
O(n*m)
songs = $("div.song").get();
for (var i = 0; i < 5; i++) {
var indexOfTop = -1;
var topRating = -1;
// find best rated song
jQuery.each(songs, function(j) {
// this line needs to be adapted for your code
var rating = $(this).text();
if (rating > topRating) {
topRating = rating;
indexOfTop = j;
}
});
// remove top item from array
if (indexOfTop == -1) {
// no items left in songs
return false;
} else {
songs.splice(indexOfTop, 1);
}
}
// remove remaining songs
$(songs).hide();
O(m*logn)
function BinaryHeap(keyFunction) {
if (arguments.length >= 1) {
this.keyFunction = keyFunction;
}
this.content = [];
}
BinaryHeap.buildHeap = function(items, keyFunction) {
var newHeap = new BinaryHeap();
if (arguments.length >= 2) {
this.keyFunction = keyFunction;
}
// slice copies the array
newHeap.content = items.slice(0);
var firstParent = Math.floor((newHeap.content.length - 1) / 2);
for (var i = firstParent; i >= 0; i--) {
newHeap._siftDown(i);
}
return newHeap;
}
BinaryHeap.prototype = {
push: function(item) {
this.content.push(item)
this._siftUp(this.content.length - 1);
},
pop: function() {
var value = this.content[0];
var newHead = this.content.pop();
if (this.content.length >= 1) {
this.content[0] = newHead;
this._siftDown(0);
}
return value;
},
// default key function, it extracts a key from the object
keyFunction: function(a) {
return a;
},
_siftDown: function(root) {
var length = this.content.length;
var k = 0;
while (root * 2 + 1 < length) {
k++;
var child = root * 2 + 1;
var rightChild = root * 2 + 2;
if (rightChild < length) {
child = this._max(child, rightChild);
}
if (this._max(root, child) == child) {
this._swap(root, child);
} else {
break;
}
root = child;
}
},
_siftUp: function(child) {
while (child >= 0) {
var root = Math.floor((child - 1) / 2);
if (this._max(child, root) == root) {
this._swap(child, root);
} else {
return;
}
child = root;
}
},
_max: function(a, b) {
return (this.keyFunction(this.content[a]) >= this.keyFunction(this.content[b])) ? a : b;
},
_swap: function(a, b) {
var buffer = this.content[a];
this.content[a] = this.content[b];
this.content[b] = buffer;
}
}
allSongs = $("div.song");
// build heap in O(n)
var myheap = BinaryHeap.buildHeap(allSongs.get(), function(item) {
return $(item).text();
});
// hide all items
allSongs.hide();
// show top 5
for (var i = 0; i < 5; i++) {
var item = myheap.pop();
// less than 5 elements
if (typeof(item) == "undefined")
break;
$(item).show();
}
O(n)
当然不可能。
Results in Milliseconds
(Mac OS X 10.6, Safari 4.0.3, 2.4 Ghz Intel Core 2 Duo)
-------
10 elements
n*logn: 3
m*n: 2
m*logn: 2
100 elements
n*logn: 26
m*n: 11
m*logn: 5
1000 elements
n*logn: 505
m*n: 140
m*logn: 42
10000 elements
n*logn: 8016
m*n: 1648
m*logn: 442
